给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 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 else
- 19 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
运行结果：
经验首页