LeetCode 101. Symmetric Tree [Easy]

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