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; }
* }
*/
我们最容易想到的，是用栈来实现：
import java.util.*;
public class Solution {
static Stack<TreeNode> stack1=new Stack<TreeNode>();
static Stack<TreeNode> stack2=new Stack<TreeNode>();
public void toStack(TreeNode p,TreeNode q)
{
while(p.left!=null)
{stack1.push(p);
p=p.left; }
while(q.left!=null)
{stack2.push(q);
q=q.left; }
stack1.push(p);
stack2.push(q); }
public boolean isSameTree(TreeNode p, TreeNode q) {
if((p==null&&q==null))
return true;
if(p==null||q==null)
return false;
while(!stack1.isEmpty())
stack1.pop();
while(!stack2.isEmpty())
stack2.pop();
TreeNode a,b;
toStack(p,q);
while(!stack1.isEmpty()&&!stack2.isEmpty())
{
a=stack1.pop();
b=stack2.pop();
if(a.val!=b.val)//判断该节点的值是否相等
return false; if((a.right!=null)&&(b.right!=null))//都有右孩子，让他们入栈
toStack(a.right,b.right); else if((a.right==null&&b.right!=null)||a.right!=null&&b.right==null)//有一个有右孩子，另外一个没有右孩子
return false;
} if(stack1.isEmpty()&&stack2.isEmpty())
return true;
return false;
} }
当然，还有更简单的，用递归搞定：
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 isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
return false;
}
更新：
上面两行
if(p == null && q == null) return true;
if(p == null || q == null) return false;
可以用一行代替：
if (p == NULL || q == NULL) return (p == q);