Leetcode: Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).



Similar Problems:


Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3
But the following [1,2,2,null,3,null,3] is not:
    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution:
// Blog link: https://code.dennyzhang.com/symmetric-tree
// Basic Ideas: BFS
// Complexity: Time O(n), Space O(n)
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

/**
 * @param root: root of the given tree
 * @return: whether it is a mirror of itself 
 */
func isSymmetric (root *TreeNode) bool {
    if root == nil { return true }
    queue := []*TreeNode{root}
    for len(queue) != 0 {
        l, l2 := []*TreeNode{}, []*TreeNode{}
        for _, node := range queue {
            if node.Left != nil { l = append(l, node.Left) }
            if node.Right != nil { l = append(l, node.Right) }
            l2 = append(l2, node.Left)
            l2 = append(l2, node.Right)
        }
        // check is sysmetric
        left, right := 0, len(l2) - 1
        for left < right {
            if l2[left] == nil || l2[right] == nil {
                if l2[left] != l2[right] { return false }
            } else {
                if l2[left].Val != l2[right].Val { return false }
            }
            left, right = left+1, right-1
        }

        queue = l
    }
    return true
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.