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
11
class Solution:
  def isSymmetric(self, root: Optional[TreeNode]) -> bool:
    def isSymmetric(p: Optional[TreeNode], q: Optional[TreeNode]) -> 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)