100.相同的树

发表于： 分类于：
字数： 498 阅读：≈ 1分钟

🌳 100.相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

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

思路

基本思想

为了辨别两棵树是否是相同的树，直接同时遍历两棵树，一旦遇到不相等就返回false，只有遍历到最后都返回true，最终的结果才是true，遍历的过程没有难点，主要是要分几种情况：

  1. 两个节点都为空：返回true
  2. 两个节点任有一个为空：返回false
  3. 两个节点值相等，当前返回true
  4. 查看两个节点的左孩子和右孩子是什么情况

上面的遍历顺序不能反，一旦到了2，说明至少有一个节点不是空，一旦到了3，说明两个节点都不是空，一旦到了四，说明两个节点的值相等

执行流程

  1. 两个节点都为空：返回true
  2. 两个节点任有一个为空：返回false
  3. 两个节点值相等，当前返回true
  4. 查看两个节点的左孩子和右孩子是什么情况

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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//到这里两个都不为空
            return (p->val==q->val)&&isSameTree(p->left,q->left)
                                    &&isSameTree(p->right,q->right);

    }
};

总结

逻辑要清晰，上一步的代码作为下一步代码的前提筛选条件