Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Solution1: recursion

如果两个结点都是null，返回true。

如果其中一个是null，说明在一棵树上结点到头，另一棵树结点还没结束，即树不相同，或者两个结点都非空，并且结点值不相同，返回false。

递归处理两个结点的左右子树，返回左右子树递归的与结果即可。

先序遍历，时间复杂度是O(n)，空间复杂度是O(logn)。

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

Reference: http://blog.csdn.net/linhuanmars/article/details/22839819
Solution2: iterative

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null)
            return true;
        
        LinkedList q1 = new LinkedList();
        LinkedList q2 = new LinkedList();
        
        q1.offer(p);
        q2.offer(q);
        
        while(!q1.isEmpty() && !q2.isEmpty()) {
            TreeNode pNode = q1.poll();
            TreeNode qNode = q2.poll();
            
            if(pNode == null) {
                if(qNode != null)
                    return false;
                else 
                    continue;
            }
            
            if(qNode == null || qNode.val != pNode.val) {
                return false;
            }
            
            q1.offer(pNode.left);
            q1.offer(pNode.right);
            q2.offer(qNode.left);
            q2.offer(qNode.right);
        }
        return true;
    }
}