算法力扣刷题记录 四十二【101. 对称二叉树、100.相同的树、572.另一个树的子树】

发布于:2024-07-11 ⋅ 阅读:(25) ⋅ 点赞:(0)

前言

二叉树篇,开始对二叉树操作练习。
记录 四十二【101. 对称二叉树】。
继续。


一、题目阅读

给你一个二叉树的根节点 root , 检查它是否轴对称

示例 1:
在这里插入图片描述

输入:root = [1,2,2,3,4,4,3]
输出:true

示例 2:
在这里插入图片描述

输入:root = [1,2,2,null,3,null,3]
输出:false

提示:

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

进阶:你可以运用递归和迭代两种方法解决这个问题吗?


二、尝试实现

思路一

先用递归试一下。核心:判断轴对称的标准是什么?

递归:自己调用自己。暂时没找到重复的逻辑

  • 判断left== right?进入到子树,不正确。
  • 左子树走左右中,右子树走右左中。序列相等?但这是对整个树。进入到子树,也不对。

思路二

改变用迭代法。用层序遍历。
获得层序结果之后,判断每一层是偶数且reverse之后相等。但对于示例二,不成立,因为空指针被排除。
思路不成立。

总结:虽然知道要找对称,但是统一判断对称的标准不会


三、参考思路

参考思路链接

学习内容

  • 轴对称:根节点的左子树和右子树是否可以翻转相等? ,如何比较?
  • 从讲解获得正确思路:本次遍历需要根节点的左子树和根节点的右子树同时遍历。一次性遍历两个子树,才能判断两边节点相不相等。
    • 先传左子树的left和右子树的right,此时外侧节点判断相等;
    • 再传左子树的right和右子树的left,此时内侧节点判断相等;
    • 两者返回之后,同时都为true,说明对称。
  • 确定遍历顺序:左右中。处理完左孩子,再处理右孩子,把结果返回给中节点。
  • 尝试实现中思路不足之处:只处理根节点左子树,发现根节点右子树的顺序和左边不一样。用遍历顺序翻转,或者如何,都得不到统一的逻辑。

递归实现

每一个注释都是思路。

/**
 * 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 iscompare(TreeNode* left,TreeNode* right){ //两边同时遍历,所以两个参数。返回是否相等,用bool类型。
        //确定终止条件
        if(!left && !right) return true;    //同时为空,可以翻转
        else if(!left && right) return false; //一个空,一个不为空。肯定不等
        else if (!right && left) return false;//一个空,一个不为空。肯定不等
        else if(left->val != right->val) return false;//都不为空,但是值不等

        //都不为空,值相等。说明可以继续进行外侧比较、内侧比较,不用return。
        bool outside = iscompare(left->left,right->right);  //同时比较,解决了左右遍历顺序不一样
        bool inside = iscompare(left->right,right->left);
        return outside && inside;   //同时返回true。才能返回true
    }
    bool isSymmetric(TreeNode* root) {
        return iscompare(root->left,root->right);
    }
};

一个树(左子树)的遍历顺序是左右中,一个树(右子树)的遍历顺序是右左中。

迭代思路1

  • 同时处理根节点左子树和根节点右子树。和之前的遍历不一样。
  • 用队列结构:把要比较的两个节点同时放入队列中,再同时取出来。判断取出来的两个节点能否翻转。所以如果左右孩子有空,也需要放到队列里。
  • 用栈结构:还是要同时处理两个节点。有两个对象要做比较。 同时放进去,再同时取出来

迭代实现【队列结构】

栈结构一样。

/**
 * 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 isSymmetric(TreeNode* root) {
        if(!root) return false;
        queue<TreeNode*> que;
        que.push(root->left);//放入左子树
        que.push(root->right);//放入右子树
        while(!que.empty()){
            TreeNode* left = que.front(); que.pop();//取出比较对象中的左节点
            TreeNode* right = que.front();que.pop();//取出比较对象中的右节点

            if(!left && !right){    //都是空节点
                continue;
            }else if(!left || !right || left->val != right->val){
                return false;
            }

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

总结【轴对称二叉树】:

  • 依然是遍历,不同在于:必须同时遍历两个子树。深入任何一个子树递归都是不对的。
  • 比较对象判断true的条件:同时空;或值相等。其余都是false。
  • 也不可以深入任何一个子树递归遍历,因为左边和右边顺序不一样。
  • 不是层序遍历。如果非得层序遍历:得出每一层结果,reverse之后看是否相等。如下(不推荐),上面的解答都很好。
/**
 * 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 isSymmetric(TreeNode* root) {
        vector<vector<int>> level;
        queue<TreeNode*> que;
        if(!root) return false;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> vec;
            while(size--){
                TreeNode* cur = que.front();que.pop();
                if(cur){ //不是空节点
                    que.push(cur->left);
                    que.push(cur->right);
                    vec.push_back(cur->val);
                }else{
                    vec.push_back(INT_MIN);//因为节点的值【-100,100】。用一个最小值代表空。
                }
            }
            level.push_back(vec);
        }
        //获得层序遍历。包含空。空的数值借助INT_MIN代替。
        for(int i = 1;i < level.size();i++){
            vector<int> temp = level[i];
            reverse(temp.begin(),temp.end());
            if(temp != level[i]){
                return false;
            }
        }
        return true;

    }
};

题目练习

【100.相同的树】

一、题目

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

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

示例 1:

输入:p = [1,2,3], q = [1,2,3]
输出:true

示例 2:

输入:p = [1,2], q = [1,null,2]
输出:false

示例 3:

输入:p = [1,2,1], q = [1,1,2]
输出:false

提示:

两棵树上的节点数目都在范围 [0, 100] 内
-10^4 <= Node.val <= 10^4

思路

判断两个树是否相同。结构相同且值相同。

  • 那么必须同时处理两个树,才有比较对象。只对一个树深入遍历/做什么操作,都是无用的 。
  • 和【101.对称二叉树】区别,比较对象。这里比较对象左孩子和左孩子比;右孩子和右孩子比。递归调用的参数给对。

代码实现

/**
 * 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 && !q) return true;  //传入节点同时为空,可以对应
        else if(!p && q) return false;//一个空,另一个不是空。不可能对应。
        else if(p && !q) return false;//一个空,另一个不是空。不可能对应。
        else if(p->val != q->val) return false;//值不等,不可能对应。

        bool leftchild = isSameTree(p->left,q->left); 
        bool rightchild = isSameTree(p->right,q->right);
        return leftchild && rightchild;
    }
};

【572.另一个树的子树】

题目

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1:

输入:root = [3,4,5,1,2], subRoot = [4,1,2]
输出:true

示例 2:

输入:root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出:false

提示:

root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-10^4 <= root.val <= 10^4
-10^4 <= subRoot.val <= 10^4

思路

(1)子树也是判断两个树相等。可以用【100.题代码实现】解决相等判断。
(2)但是得在root中找到等于subRoot根节点值的节点,作为子树的根节点。用层序遍历root。

代码实现

/**
 * 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 isSame(TreeNode* rootnode,TreeNode* subRootnode){
        if(!rootnode && !subRootnode) return true;
        else if(!rootnode && subRootnode) return false;
        else if(rootnode && !subRootnode) return false;
        else if(rootnode->val != subRootnode->val) return false;

        bool leftchild = isSame(rootnode->left,subRootnode->left);
        bool rightchild = isSame(rootnode->right,subRootnode->right);
        return leftchild && rightchild;
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        //先找到和subRoot值相等的节点,才有可能相等。得遍历root找到和subRoot值相等的节点,可能作为子树的根节点

        //用层序遍历
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            while(size--){
                TreeNode* cur = que.front();que.pop();
                if(cur->val == subRoot->val){
                    bool subtree = isSame(cur,subRoot);
                    if(subtree) return true;
                }
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
        }
        return false;
    }
};

全文总结

核心:同时遍历两个树,确定比较对象。进行递归实现。

深入任何一个树遍历,都无法产生比较对象的双方。

(欢迎指正,转载标明出处)