https://leetcode.com/problems/symmetric-tree/

这次来看一道树的题型。虽然说是简单题,但是想要快速写出来,并实现递归和迭代两种方法,需要对树的遍历足够熟悉。最近我就是有一个面试挂在这道题上了,实在是不应该,说多了都是泪。

不对称有两种情况:要么是一边有子结点一边没有,或者是都有结点,但是值不相等。要注意这两个判断的顺序,如果反了的话,会出现取不存在的结点的 val 的情况,会报错。

特殊情况,如果是叶子结点,没有子结点,返回 true。如果是空树,也返回 True

递归解法

# 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: TreeNode) -> bool:

        def helper(left, right):
            if not left and not right: return True
            if (left and not right) or (right and not left):
                return False
            return left.val == right.val and helper(left.left, right.right) and helper(left.right, right.left)

        if not root: return True
        return helper(root.left, root.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: TreeNode) -> bool:

        if not root: return True

        s = [(root.left, root.right)]

        while s:
            left, right = s.pop()

            if not left and not right:
                continue

            if (left and not right) or (right and not left):
                return False

            if left.val != right.val:
                return False

            s.append((left.left, right.right))
            s.append((left.right, right.left))

        return True