485，递归和非递归两种方式解相同的树

Original 山大王wld 数据结构和算法 2022-05-11

收录于合集 #算法图文分析 161个

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}