LeetCode：101. Symmetric Tree（判断该树是不是对称树）

ゝ一纸荒年。 2022-04-11 13:30 156阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k][LeetCode_560. Subarray Sum Equals K_k][）][Leetcode_300. Longest Increasing Subsequence]**

--------------------

### 题目描述 ###

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 \[1,2,2,3,4,4,3\] 是对称的。

1
       / \
      2   2
     / \ / \
    3  4 4  3

但是下面这个 \[1,2,2,null,3,null,3\] 则不是镜像对称的:

1
       / \
      2   2
       \   \
       3    3

来源：力扣（LeetCode）

--------------------

### java实现方法1： ###

/**
         * 判断该二叉树是不是对称的
         *
         * @param root 二叉树
         * @return 布尔值
         */
        public boolean isSymmetric(TreeNode root) {
            if (root == null) {
                return true;
            }
            return helper(root.right, root.left);
        }
    
        /**
         * 帮助类
         *
         * @param t1 t1
         * @param t2 t2
         * @return 布尔值
         */
        private boolean helper(TreeNode t1, TreeNode t2) {
            if (t1 == null && t2 == null) {
                return true;
            }
            if (t1 == null || t2 == null) {
                return false;
            }
            if (t1.val != t2.val) {
                return false;
            }
            return helper(t1.left, t2.right) && helper(t1.right, t2.left);
        }

时间复杂度：O(n)

空间复杂度：O(n)

--------------------

### python实现方法1： ###

def is_symmetric(self, root: TreeNode) -> bool:
            '''
                判断两棵树是否相同
            Args:
                root: 根节点
            Returns:
                布尔值
            '''
            if not root:
                return True
            return self.search_helper(root.left, root.right)
    
    def search_helper(self, t1: TreeNode, t2: TreeNode) -> bool:
            '''
                判断是否是对称二叉树
            Args:
                t1: 二叉树t1
                t2: 二叉树t2
            Returns:
                布尔值
            '''
            if not t1 and not t2:
                return True
            if not t1 or not t2:
                return False
            if t1.val != t2.val:
                return False
            return self.search_helper(t1.left, t2.right) and self.search_helper(t1.right, t2.left)

时间复杂度：O(n)

空间复杂度：O(n)

--------------------

### java实现方法2： ###

/**
    * 判断该二叉树是不是对称
    *
    * @param root 二叉树
    * @return 布尔值
    */
    public boolean isSymmetric2(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        q.add(root);
        while (!q.isEmpty()) {
              TreeNode t1 = q.poll();
              TreeNode t2 = q.poll();
              if (t1 == null && t2 == null) {
                  continue;
              }
              if (t1 == null || t2 == null) {
                  return false;
              }
              if (t1.val != t2.val) {
                  return false;
              }
              q.add(t1.left);
              q.add(t2.right);
              q.add(t1.right);
              q.add(t2.left);
            }
            return true;
        }

时间复杂度：O(n)

空间复杂度：O(n)

--------------------

### python实现方法2： ###

def is_symmetric2(self, root: TreeNode) -> bool:
          '''
               判断二叉树是否是对称
          Args:
               root: 根节点
          Returns:
               布尔值
          '''
          queue = []
          queue.append(root)
          queue.append(root)
          while queue:
              r1 = queue.pop()
              r2 = queue.pop()
              if not r1 and not r2:
                  continue
              if not r1 or not r2:
                  return False
              if r1.val != r2.val:
                  return False
              queue.append(r1.left)
              queue.append(r2.right)
              queue.append(r1.right)
              queue.append(r2.left)
          return True

时间复杂度：O(n)

空间复杂度：O(n)

--------------------

### 源码地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode