[LeetCode] 101. Symmetric Tree

Posted on | In

Problem

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
3
4
5
    1
   / \
  2   2
 / \ / \
3  4 4  3

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

1
2
3
4
5
    1
   / \
  2   2
   \   \
   3    3

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

Explanation 1

  1. In recursive method, from the above example, we don’t need to check the root node first. We can think of comparing the root.left subtree and root.right subtree are symmetric. We need to meet three conditions if they are symmetric.

    1. Left and right subtree’s root value are equal (2 == 2)
    2. Left subtree’s left value is equal to right subtree’s right value (3 == 3)
    3. Left subtree’s right value is equal to right subtree’s left value (4 == 4)

  2. We can recursivly call the above helper method to if left subtree’s left tree with right subtree’s right tree are symmertric, and also left subtree’s right tree with right subtree’s left tree are symmetric.

  3. The base case is when both values are null, we return true; else we return false. If the values are not equal, we also return false.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    boolean helper(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        return (left.val == right.val) && (helper(left.left, right.right) && helper(left.right, right.left));
    }
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return helper(root.left, root.right);
    }
}

Explanation 2

  1. In iterative method, we can use a stack to push left subtree’s left value then push rigth subtree’s right value (these 2 values a group), also push left subtree’s right value and then push right subtree’s left value (these 2 values as a group). Then, we pop a group’s two value and compare this group’s two values are equal or not.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        Stack<TreeNode> st = new Stack<>();
        TreeNode left = root.left;
        TreeNode right = root.right;
        st.push(left);
        st.push(right);
        while (!st.isEmpty()) {
            right = st.pop();
            left = st.pop();
            if (left == null && right == null) continue;
            if (left == null || right == null || left.val != right.val) return false;
            st.push(left.left);
            st.push(right.right);
            st.push(left.right);
            st.push(right.left);
        }

        return true;
    }
}