相同的树-力扣

这道题目与堆成二叉树题目很相似,对称二叉树是每次传入的节点组合是 《左子树的左节点 和 右子树的 右节点》 《左子树的右节点 和 右子树的左节点》, 而这道题就更加简单,传入两棵树的左节点和右节点即可。

/**
 * 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;
        }
        bool l_tree = isSameTree(p->left, q->left);
        bool r_tree = isSameTree(p->right, q->right);
        return l_tree && r_tree;
    }
};

尝试使用迭代法来完成这道题目,通过队列每次出队两个元素,并对其进行比较,从而判断两个树是否相等。
尽管代码思路很简单,但在实现时,一开始习惯性的写成了层序遍历那样,在将子节点入队时,判断了子节点不为空才让子节点入队,导致出现误判的情况。这里即使是空节点,也是需要入队进行比较的,因为一个树的这个节点为空,但另一棵树对应的这个节点可不一定。


class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue<TreeNode*> que;
        if(p != nullptr && q != nullptr){
            que.push(p);
            que.push(q);
        }else if(p == nullptr && q == nullptr){
            return true;
        }else{
            return false;
        }
        while(!que.empty()){
            TreeNode* node1 = que.front();
            que.pop();
            TreeNode* node2 = que.front();
            que.pop();
            
            if(node1 == nullptr && node2 == nullptr){
                continue;
            }
            if(node1 == nullptr || node2 == nullptr){
                return false;
            }
            if(node1->val != node2->val){
                return false;
            }

            que.push(node1->left);
            que.push(node2->left);
            que.push(node1->right);
            que.push(node2->right);
        }
        return true;
    }
};

相关推荐

  1. 相同-

    2024-06-09 17:14:04       7 阅读
  2. 0100——相同

    2024-06-09 17:14:04       34 阅读
  3. 572. 另一棵

    2024-06-09 17:14:04       34 阅读
  4. 每日一题】145二叉后序遍历

    2024-06-09 17:14:04       34 阅读

最近更新

  1. 探索机器学习:深入理解Sklearn基础

    2024-06-09 17:14:04       0 阅读
  2. vue3delete请求报403forbidden,前后端解决方式

    2024-06-09 17:14:04       0 阅读
  3. Vue小记——如何理解 $nextTick( ) ?

    2024-06-09 17:14:04       0 阅读
  4. IDM(Internet Download Manager)简介

    2024-06-09 17:14:04       0 阅读
  5. 深度神经网络是什么?

    2024-06-09 17:14:04       0 阅读
  6. 设计模式-组合模式Composite(结构型)

    2024-06-09 17:14:04       0 阅读
  7. 使用 Python进行自动备份文件

    2024-06-09 17:14:04       0 阅读
  8. React <> </>的用法

    2024-06-09 17:14:04       0 阅读

热门阅读

  1. TypeScript常见面试题第十一节

    2024-06-09 17:14:04       3 阅读
  2. TalkingData数据统计:洞察数字世界的关键工具

    2024-06-09 17:14:04       4 阅读
  3. Django中drf动态过滤查询

    2024-06-09 17:14:04       7 阅读
  4. 006 RabbitMQ

    2024-06-09 17:14:04       6 阅读
  5. 记录一次jlink连不上cpu的情况

    2024-06-09 17:14:04       6 阅读
  6. wordpress网站建设详细过程

    2024-06-09 17:14:04       5 阅读
  7. 移动端前端开发遇到过的Andorid和IOS的差异记录

    2024-06-09 17:14:04       5 阅读
  8. Audio音频资源播放

    2024-06-09 17:14:04       4 阅读