101.md

101. 对称二叉树

思路

• 对称的二叉树，所有节点数值对称比较，一定相同。所以需要找到一个能对称比较节点数值的方法。

          1
       /      \
     2         2
    / \       / \
   3   4     4   3
  / \ / \   / \ / \ 
 5  6 7  8 8  7 6  5
  \               /
  9               9

• 要实现 2 跟 2 比较、3 跟 3 比较、4 跟 4 比较、5 跟 5 比较 ... 9 跟 9 比较

• 即：

  root.left.val vs root.right.val
  root.left.left.val vs root.right.right.val
  root.left.right.val vs root.right.left.val
  root.left.left.left.val vs root.right.right.right.val
  ...
  root.left.left.left.right.val vs root.right.right.right.left.val

• 上面这些比较可以转换为一个递归，递归只做一件事：比较

# Python3
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        return self.isSameVal(root.left,root.right)
    def isSameVal(self, left: TreeNode, right: TreeNode) -> bool:
        if left.val == right.val:
            return self.isSameVal(left.right, right.left) and self.isSameVal(left.left, right.right)
        else:
            return False

• 注意理解这个递归能实现对称一一比较
• 传入的参数是树节点，虽然比较的是树节点的值是否相同，但对于传入树节点来说，比较的是是否互为镜像，所以将 isSameVal 改为 isMirror 更符合语境。
• 这道题是 100 题的变异版，左左比较、右右比较变为左右、右左比较
• 时间复杂度：O(N)，N 为树的节点数量（算上 null 节点），比较次数为 N/2
• 空间复杂度：O(1)，没有利用额外空间
• 标签：递归

代码

# Python3
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root == None:
            return True
        return self.isMirror(root.left, root.right)
    def isMirror(self, left: TreeNode, right: TreeNode) -> bool:
        if left == None and right == None:
            return True
        if left == None or right == None:
            return False
        if left.val == right.val:
            return self.isMirror(left.right, right.left) and self.isMirror(left.left, right.right)
        else:
            return False;

// Java
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isMirror(root.left, root.right);
    }
    
    public boolean isMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        
        if (left == null || right == null) return false;
        
        if (left.val == right.val) {
            return isMirror(left.right, right.left) && isMirror(left.left, right.right);
        } else {
            return false;
        }
    }
}

错误思路：比较左右子树的中序遍历是否相同

代码

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

[1,2,2,3,4,4,3]

• 左：中根遍历 3,2,4
• 右：中根遍历 4,2,3

    1
   / \
  2   2
   \   \
   3    3
   
[1,2,2,null,3,null,3]

• 左：中根遍历 2,3
• 右：中根遍历 2,3

          1
       /      \
     2         2
    / \       / \
   3   4     4   3
  / \ / \   / \ / \ 
 5  6 7  8 8  7 6  5
 
[1,2,2,3,4,4,3,5,6,7,8,8,7,6,5]

• 左：中根遍历 5,3,6,2,7,4,8
• 右：中根遍历 8,4,7,2,6,3,5

          1
       /      \
     2         2
      \       /
       4     4  
      / \   / \ 
      7  8 8  7 
      
[1,2,2,null,4,4,null,null,null,7,8,8,7,null,null]

• 左：中根遍历 2,7,4,8 2,null,7,4,8
• 右：中根遍历 8,4,7,2 8,4,7,2,null

    1
   / \
  2   2
 /   / 
2   2

[1,2,2,2,null,2]

• 左：中根遍历 2,2,null
• 右：中根遍历 2,2,null

          5
       /      \
     4         1
      \         \ 
       1         4  
      /         / 
     2         2

[5,4,1,null,1,null,4,2,null,2,null]

• 左：中根遍历 null,4,2,1,null
• 右：中根遍历 null,1,2,4,null

代码

# Python3
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root == None:
            return True
        if root.left == None and root.right == None:
            return True
        if root.left == None or root.right == None:
            return False
        arrl, arrr = [],[]
        if root.left != None:
            self.helper(root.left,arrl)
            print(arrl)
        if root.right != None:
            self.helper(root.right,arrr)
            print(arrr[::-1])
        return arrl == arrr[::-1]
    def helper(self, root:TreeNode, arr: List[int]):
        if root.left != None:
            self.helper(root.left,arr)
        elif root.right != None:
            arr.append(None)
        arr.append(root.val)
        if root.right != None:
            self.helper(root.right,arr)
        elif root.left != None:
            arr.append(None)