100. 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.

/**
 * 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 isSameTree(TreeNode p, TreeNode q) 
    {

    }       
}
        

Solution:

一开始我的想法是，分别求两棵树的前序和中序遍历，然后两两对比。如果完全一致则可判定这两棵树是相同的。（感觉有点繁琐，有待验证可行性）

后来Google了一下发现可以用递归的思路来做。具体思路是：如果p树的当前节点的val与q树中当前节点的val相等，且p树中当前子树的左、右子树和q树中当前子树的左、右子树相同，则p、q树中，以当前节点为跟节点的两棵树相同。

代码如下：

/**
 * 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 isSameTree(TreeNode p, TreeNode q) 
    {
        if(p == null && q == null)
            return true;
        else if((p == null && q != null) || (p != null && q == null))
            return false;
        else // in this case, both p and q are not null
        {
            // so we compare their value
            if(p.val != q.val)
                return false;
            else // p.val == q. val, so we move forawrd to their children
            {
                boolean leftChildResult, rightChildResult;
                leftChildResult = isSameTree(p.left, q.left);
                rightChildResult = isSameTree(p.right, q.right);
                return leftChildResult & rightChildResult; // only when both of their left and right subtree are same, this two trees are same.
            }
        }
    }       
}

参考：
http://blog.csdn.net/u200814499/article/details/40076041