其他
485,递归和非递归两种方式解相同的树
It takes more than intelligence to act intelligently.
头脑聪明不代表就能明智地行事。
问题描述
给定两个二叉树,编写一个函数来检验它们是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例 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
递归解法
这题是让判断两棵树是否相同,最简单的方式就是使用递归。先判断根节点是否相同,如果相同再分别判断左右子节点是否相同,判断的过程中只要有一个不相同就返回false,如果全部相同才会返回true。
来看下代码
1public boolean isSameTree(TreeNode p, TreeNode q) {
2 //如果都为空我们就认为他是相同的
3 if (p == null && q == null)
4 return true;
5 //如果一个为空,一个不为空,很明显不可能是相同的树,直接返回false即可
6 if (p == null || q == null)
7 return false;
8 //如果这两个节点都不为空并且又不相等,所以他也不可能是相同的树,直接返回false
9 if (p.val != q.val)
10 return false;
11 //走到这一步说明节点p和q是完全相同的,我们只需要在比较他们的左右子节点即可
12 return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
13}
非递归解决
非递归解决可以参照树的BFS遍历,也就是宽度优先搜索,也称广度优先搜索。关于树的BFS遍历可以参照373,数据结构-6,树,他是一层一层遍历的,如下图所示
二叉树的BFS代码如下
1public void bfsPrint(TreeNode tree) {
2 if (tree == null)
3 return;
4 Queue<TreeNode> queue = new LinkedList<>();
5 queue.add(tree);//相当于把数据加入到队列尾部
6 while (!queue.isEmpty()) {
7 //poll方法相当于移除队列头部的元素
8 TreeNode node = queue.poll();
9 System.out.println(node.val);
10 if (node.left != null)
11 queue.add(node.left);
12 if (node.right != null)
13 queue.add(node.right);
14 }
15}
他使用的是一个队列,把每层的结点不停的放入到队列中,然后再出队,再把子节点放入到队列中……
对于这道题我们可以使用两个队列,一个是存放第一棵树节点的队列,一个是存放第二棵树节点的队列。
1,每次这两个队列的元素同时出队,出队之后都要判断出队的这两个节点值是否相同,如果不相同直接返回false,如果相同再往下走。
2,然后再判断他们的左子节点是否都存在,如果一个存在一个不存在就直接返回false,如果都存在就加入到队列中
3,右子节点同左子节点
4,最后再判断这两个队列是否都为空
原理比较简单,看下代码
1public boolean isSameTree(TreeNode p, TreeNode q) {
2 //如果都为空我们就认为他们是相同的
3 if (p == null && q == null)
4 return true;
5 //如果一个为空,一个不为空,很明显不可能是相同的树,直接返回false即可
6 if (p == null || q == null)
7 return false;
8 Queue<TreeNode> queueP = new LinkedList<>();
9 Queue<TreeNode> queueQ = new LinkedList<>();
10 //如果p和q两个节点都不为空,就把他们加入到队列中
11 queueP.add(p);
12 queueQ.add(q);
13 while (!queueP.isEmpty() && !queueQ.isEmpty()) {
14 //分别出队
15 TreeNode tempP = queueP.poll();
16 TreeNode tempQ = queueQ.poll();
17 //如果这两个节点的值不相同,直接返回false
18 if (tempP.val != tempQ.val)
19 return false;
20
21 //如果对应的左子节点不为空就加入到队列中
22 if (tempP.left != null)
23 queueP.add(tempP.left);
24 if (tempQ.left != null)
25 queueQ.add(tempQ.left);
26 //注意这里没有直接判断两个左子节点是否一个为空一个
27 //不为空,而是通过队列的长度来判断的,只有两个左子节点
28 //都为空或者都不为空的时候,队列长度才会一样
29 if (queueP.size() != queueQ.size())
30 return false;
31
32 //右子节点同上
33 if (tempP.right != null)
34 queueP.add(tempP.right);
35 if (tempQ.right != null)
36 queueQ.add(tempQ.right);
37 if (queueP.size() != queueQ.size())
38 return false;
39 }
40 //最后再判断这两个队列是否都为空
41 return queueP.isEmpty() && queueQ.isEmpty();
42}
总结
我们从代码层面可以看到第一种方式要简单的多,当然第二种解法也提供了一种思路。
长按上图,识别图中二维码之后即可关注。
如果觉得有用就点个"赞"吧