Skip to content

101. Symmetric Tree

https://leetcode.com/problems/symmetric-tree/

js
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
function isSymmetric(root) {
  const symmetric = (left, right) => {
    if (!left && !right) {
      return true
    }
    if (!left || !right) {
      return false
    }
    return left.val === right.val &&
      symmetric(left.left, right.right) &&
      symmetric(left.right, right.left)
  }

  return symmetric(root, root)
}
js
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
function isSymmetric(root) {
  const queue = [root, root]

  while (queue.length) {
    const p = queue.shift()
    const q = queue.shift()

    if (!p && !q) {
      continue
    }
    if (!p || !q) {
      return false
    }
    if (p.val !== q.val) {
      return false
    }

    queue.push(p.left, q.right, p.right, q.left)
  }

  return true
}
py
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution(object):

    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.symmetric(root, root)

    def symmetric(self, left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        return left.val == right.val and self.symmetric(left.left, right.right) and self.symmetric(left.right, right.left)
py
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution(object):

    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        queue = [root, root]

        while queue:
            p, q = queue[0], queue[1]
            queue = queue[2:]

            if not p and not q:
                continue
            if not p or not q:
                return False
            if p.val != q.val:
                return False

            queue += [p.left, q.right, p.right, q.left]

        return True
go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    return symmetric(root, root)
}

func symmetric(t1 *TreeNode, t2 *TreeNode) bool {
    if t1 == nil && t2 == nil {
        return true
    }
    if t1 == nil || t2 == nil {
        return false
    }
    return t1.Val == t2.Val && symmetric(t1.Left, t2.Right) && symmetric(t1.Right, t2.Left)
}
go
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    q := []*TreeNode{root, root}

    for len(q) > 0 {
    	t1, t2 := q[0], q[1]
    	q = q[2:]

    	if t1 == nil && t2 == nil {
    		continue
    	}
    	if t1 == nil || t2 == nil {
    		return false
    	}
    	if t1.Val != t2.Val {
    		return false
    	}

    	q = append(q, []*TreeNode{t1.Left, t2.Right, t1.Right, t2.Left}...)
    }

    return true
}