【面试经典150 | 二叉树】相同的树

文章目录

写在前面
Tag
题目来源
题目解读
解题思路
- 方法一：递归
- 方法二：迭代
写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

Tag：介绍本题牵涉到的知识点、数据结构；
题目来源：贴上题目的链接，方便大家查找题目并完成练习；
题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【递归】【迭代】【二叉树】

题目来源

100. 相同的树

题目解读

判断两棵二叉树是否相同，相同不仅要在结构上相同还要在对应节点值上相同。

解题思路

有两种解决思路，一是递归而是迭代。

在真正理解的递归的含义之后，会发现不论是从代码量还是思考量递归算法都更胜一筹。而迭代虽易于理解，但是代码量较大。

方法一：递归

思路

我们从根节点开始判断两棵二叉树是否相同，可以发现如果根节点的值相同，并且结构相同（左右子树都有），那么只需要判断两棵树的左右子树是否相同即可。

标准的大问题转化成了子问题，都是判断两棵树是否相同，只是范围缩小了。于是可是使用递归来解题。

递归出口是什么？

递归出口换言之就是可以直接进行判断的情况，包括：

节点都为空，此时可以直接返回 true；
一个节点为空，另一个不为空，返回 false；
节点值不相等，返回 false。

大问题与子问题的如何链接？

本题是判断二叉树是否相同，如果对应的子二叉树不同，则 “大” 二叉树也不同。

算法

我们从根节点开始递归，递归函数为：

递归出口，见上述对递归出口的描述；
递归比较左子树和右子树，“大问题” 的比较结果即为小问题的比较结果。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == nullptr && q == nullptr){
            return true;
        }
        else if(p == nullptr || q == nullptr){
            return false;
        }
        else if(p->val != q->val){
            return false;
        }
        else{
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        }
    }
};

复杂度分析

时间复杂度： $O (min (m, n))$ ， $m$ 和 $n$ 分别为两个二叉树的节点数。

空间复杂度： $O (min (m, n))$ 。

方法二：迭代

思路

递归是隐式的进行比较，而迭代是显示的比较。

通过迭代判断两个二叉树是否相同。同样首先判断两个二叉树是否为空，如果两个二叉树都不为空，则从两个二叉树的根节点开始广度优先搜索。

接着使用两个队列分别按层存储两棵二叉树的节点。初始时将两个两棵树的根节点分别加入两个队列。每次从两个队列各取出一个节点，进行如下比较操作：

比较两个节点的值，如果两个节点的值不相同则两棵二叉树一定不同；
如果两个节点的值相同，则判断两个节点的子节点是否为空，如果只有一个节点的左子节点为空，或者只有一个节点的右子节点为空，则两个两棵树的结构不同，因此两棵二叉树一定不同；
如果两个节点的子节点的结构相同，则将两棵节点的非空子节点分别加入两个队列，子节点加入队列时需要注意顺序，如果左右子节点都不为空，则先加入左子节点，后加入右子节点。

如果搜索结束时两个队列同时为空，则两棵二叉树相同。如果只有一个队列为空，则两棵二叉树的结构不同，因此两棵二叉树不同。

算法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == nullptr && q == nullptr){
            return true;
        }
        else if(p == nullptr || q == nullptr){
            return false;
        }

        queue<TreeNode*> q1, q2;
        q1.push(p);
        q2.push(q);
        
        while(!q1.empty() && !q2.empty()){
            TreeNode* now1 = q1.front();
            q1.pop();
            TreeNode* now2 = q2.front();
            q2.pop();

            // 两个节点值不同
            if(now1->val != now2->val){
                return false;
            }

            auto left1 = now1->left, right1 = now1->right, left2 = now2->left, right2 = now2->right;
            // 左/右子树一个为空，另一个不为空
            if((left1 == nullptr) ^ (left2 == nullptr)){
                return false;
            } 
            if((right1 == nullptr) ^ (right2 == nullptr)){
                return false;
            }
            
            // 更新队列
            if(left1)  q1.push(left1);
            if(right1) q1.push(right1);
            if(left2)  q2.push(left2);
            if(right2) q2.push(right2);
        }
        return q1.empty() && q2.empty();
    }
};