101. Symmetric Binary Tree

101. Symmetric Binary Tree (Easy) 对称二叉树

题干

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]
Output: false

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• -100 <= Node.val <= 100

Follow up: Could you solve it both recursively and iteratively?

解法

递归解法

核心思路：将根节点的左右子树递归对称对比，单个节点的对比包含以下规则：

• 两个节点都为None的时候，是对称的
• 两个节点只有一个是None的时候，不对称
• 两个节点都不是None，value不相同的时候，不对称
• 两个节点都不是None，节点value相同，并且左右子树递归对称的时候，对称

递归实现：

• 输入参数：两个Optional[TreeNode]
• 输出参数：bool
• 终止条件：
  • 两个节点都是None，返回True
  • 只有一个是None，返回False
  • 两个节点不为None，value不同，返回False
• 单层核心逻辑：
  • 节点1的左子树和节点2的右子树对比
  • 节点1的右子树和节点2的左子树对比
  • 节点1和节点2的对比

两个节点的val对比属于终止条件，并不是中节点的比较，因为节点的比较，除了val之外，还有left和right的对比。

单层核心逻辑，左右中是后序遍历。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True
        return self.isSame(root.left, root.right)
    
    def isSame(self, node_01: Optional[TreeNode], node_02: Optional[TreeNode]) -> bool:
        # 终止条件
        if not node_01 and not node_02:
            return True
        if not node_01 or not node_02:
            return False
        if node_01.val != node_02.val:
            return False
        
        # 后序处理，左右中（中隐藏在return的逻辑里面了）
        # 注意，中是指中节点，当前节点的val对比并不是中节点完整的逻辑对比，所以不算中
        if not self.isSame(node_01.left, node_02.right):
            return False
        if not self.isSame(node_01.right, node_02.left):
            return False
        return True