给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

 

示例 1:

输入:     1         1          / \       / \         2   3     2   3        [1,2,3],   [1,2,3]输出: true

示例 2:

输入:     1         1          /           \         2             2        [1,2],     [1,null,2]输出: false

示例 3:

输入:     1         1          / \       / \         2   1     1   2        [1,2,1],   [1,1,2]输出: false 通过此题掌握树的运用 题目分析：比较两棵树是不是相等；树的相等包括节点上的值对应相等，以及具有相同的结构； 我们运用递归的思想解决此题； 代码实现：

1 public static class TreeNode 2     { 3         int data; 4         TreeNode left; 5         TreeNode right; 6         TreeNode(int val) 7         { 8             data = val; 9         }10     }11 12     public boolean isSameTree(TreeNode p, TreeNode q)13     {14         if (p == null && q == null)15             return true;16         else if (p == null || q == null)17             return false;18         else19             return (p.data == q.data && isSameTree(p.left, q.left) && isSameTree(p.right, q.right));20     }

通过上述代码可以看出：先考虑树为空的情况；如果两棵树都为空，则相等；如果两棵树中只有一棵树为空，则不相等；之后比较两棵树的根结点是否相等；然后运用递归的方法对两棵树的左子树和右子树分别比较，如果左子树和右子树对应相等，则这两棵树相等；

 

主函数：

1 public static void main(String[] args) 2     { 3         TreeNode p = new TreeNode(1); 4         p.left = new TreeNode(2); 5         p.right = null; 6  7         TreeNode q = new TreeNode(1); 8         q.left = null; 9         q.right = new TreeNode(3);10 11         Tree2 t = new Tree2();12         System.out.println(t.isSameTree(p, q));13     }

我构造的两棵树如下所示：

1         1          /           \         2             2

 

运行结果：

1 false