Skip to content

101. Symmetric Tree 👍

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  bool isSymmetric(TreeNode* root) {
    return isSymmetric(root, root);
  }

 private:
  bool isSymmetric(TreeNode* p, TreeNode* q) {
    if (!p || !q)
      return p == q;

    return p->val == q->val &&                //
           isSymmetric(p->left, q->right) &&  //
           isSymmetric(p->right, q->left);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
  public boolean isSymmetric(TreeNode root) {
    return isSymmetric(root, root);
  }

  private boolean isSymmetric(TreeNode p, TreeNode q) {
    if (p == null || q == null)
      return p == q;

    return p.val == q.val && isSymmetric(p.left, q.right) && isSymmetric(p.right, q.left);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
  def isSymmetric(self, root: TreeNode | None) -> bool:
    def isSymmetric(p: TreeNode | None, q: TreeNode | None) -> bool:
      if not p or not q:
        return p == q
      return (p.val == q.val and
              isSymmetric(p.left, q.right) and
              isSymmetric(p.right, q.left))

    return isSymmetric(root, root)