101. Symmetric Tree

Loading...LeetCode

Tree特定层内部的比较，肯定先想到level order traversal，那就直接BFS。

但既然在练习DFS，就把DFS也写一下吧...这边不太一样的是每次加进stack的不是单个node，而是当前node pair分别的左右配对，这样就可以一直比较左右对称位置的node val。

BFS

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        q = collections.deque([root])
        while q:
            n = len(q)
            level = []
            for _ in range(n):
                node = q.popleft()
                if node:
                    level.append(node.val)
                    q.append(node.left if node.left else None)
                    q.append(node.right if node.right else None)
                else:
                    level.append(None)
            for i in range(len(level)//2):
                if level[i] != level[-1-i]: return False
        return True

DFS

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root: return True
        stack = collections.deque([(root.left, root.right)])
        while stack:
            l, r = stack.pop()
            if not l and not r: continue
            if not l or not r or l.val != r.val: return False
            stack.append((l.left, r.right))
            stack.append((l.right, r.left))
        return True

DFS Recursive

class Solution:
    def dfs(self, l, r):
        if l and r:
            # 当前配对相等，外子配对相等，内子配对相等
            return all((l.val == r.val, self.dfs(l.left, r.right), self.dfs(l.right, r.left)))
        elif not l and not r: return True
        elif not l or not r: return False
        
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root: return True
        return self.dfs(root.left, root.right)