101.Symmetric Tree

tags: Easy,Tree,DFS,BFS

101. Symmetric Tree

題目描述

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?

解答

Python

• DFS

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def isMirror(t, r):
            if not t and not r:
                return True

            if t and r and t.val == r.val:
                return isMirror(t.left, r.right) and isMirror(t.right, r.left)

            return False

        return isMirror(root.left, root.right)

• BFS

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        q = deque([root, root])

        while q:
            t = q.popleft()
            r = q.popleft()

            if not t and not r: 
                continue
            if not t or not r or t.val != r.val: 
                return False

            q.append(t.left)
            q.append(r.right)
            q.append(t.right)
            q.append(r.left)

        return True

Ron ChenMon, Mar 13, 2023

Javascript

function isSymmetric(root) {
  if (!root) return true;
  const queue = [root.left, root.right];
  while (queue.length) {
    const left = queue.shift();
    const right = queue.shift();
    if (!left && !right) continue;
    if (!left || !right) return false;
    if (left.val !== right.val) return false;

    queue.push(left.left, right.right, left.right, right.left);
  }

  return true;
}

MarsgoatMon, Mar 13, 2023

Reference

回到題目列表