野球拳刷刷刷: 101. Symmetric Tree

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:

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

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

Solution:

Method 1: recursive

We recursively check if the subtrees are symmetric.

Given p and q, to check if p and q are symmetric trees, we check:

1. p.val == q.val

2. p.left and p.right are symmetric trees

3. p.right and q.left are symmetric trees

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isMirror(root.left, root.right);
    }
    
    public boolean isMirror(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && 
               isMirror(p.left, q.right) && 
               isMirror(p.right, q.left);
    }
}

Method 2: iterative

The ideas is to use stack to store nodes from two trees. And every time we pop two of them and compare the value.

When we push, we push the left node of p and right node of q, or we push the right node of p and left node of q.

The nodes are pushed into the stack in pairs, so if the size of stack mod 2 is not zero, it must not be symmetric.

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        Stack<TreeNode> stack = new Stack<>();
        if (!addNode(root.left, root.right, stack)) {
            return false;
        }
        while (!stack.isEmpty()) {
            if (stack.size() % 2 != 0) {
                return false;
            }
            TreeNode p = stack.pop();
            TreeNode q = stack.pop();
            if (p.val != q.val) {
                return false;
            }
            if (!addNode(p.left, q.right, stack)) {
                return false;
            }
            if (!addNode(p.right, q.left, stack)) {
                return false;
            }
        }
        return true;
    }
    
    public boolean addNode(TreeNode p, TreeNode q, Stack<TreeNode> stack) {
        if (p == null &&  q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        stack.push(p);
        stack.push(q);
        return true;
    }
}

Saturday, May 6, 2017

101. Symmetric Tree