算法 二叉树2 || 层序遍历 226.翻转二叉树 101. 对称二叉树 104.二叉树的最大深度 111 二叉树的最小深度 222.完全二叉树的节点个数

102 二叉树的层序遍历

队列先进先出,符合一层一层遍历的逻辑,而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而这种层序遍历方式就是图论中的广度优先遍历,只不过我们应用在二叉树上。
在这里插入图片描述

迭代法:

/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> que;
        if(root == nullptr) return {};
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> vec;
            for(int i = 0; i < size; ++i){
                TreeNode* cur = que.front();
                que.pop();
                vec.push_back(cur->val);
                if(cur->left)  que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
            res.push_back(vec);
        }
        return res;
    }
};

递归法:
递归在遍历的时候,会一层层下去,不能像队列一样遍历一层处理一层。所以递归法层序遍历可以使用变量depth来协助指明当前元素的深度。因为存放元素的容器是二维数组,横向的顺序可以根据左右元素的处理顺序决定,纵向则可以使用depth来控制
其中注意这一行:
if (result.size() == depth) result.push_back(vector());
递归一路向左遍历,遇到每一行的最左边的第一个值才重新创建一行。
在这里插入图片描述

class Solution {
public:
    void order(TreeNode* cur, vector<vector<int>>& result, int depth)
    {
        if (cur == nullptr) return;
        if (result.size() == depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};

107.二叉树的层次遍历 II

很简单,把102的res 反转一下就行

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        reverse(result.begin(), result.end()); // 在这里反转一下数组即可
        return result;

    }
};

199.二叉树的右视图

注意题意:是右视图,而不是只看最右侧的节点。所以下面这个二叉树返回的应该是1 3 4而不是 1 3。在遍历的时候依旧要遍历左子树,只是返回每一层最右侧的值即可。
在这里插入图片描述

/**
 * 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:
    vector<int> rightSideView(TreeNode* root) {
        if(root == nullptr) return {};
        vector<int> res;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            for(int i = 0; i<size; i++){
                TreeNode* cur = que.front();
                que.pop();
                if(i == size-1) res.push_back(cur->val);
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            } 
        }
        return res;
    }
};

637.二叉树的层平均值

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<double> result;
        while (!que.empty()) {
            int size = que.size();
            double sum = 0; // 统计每一层的和
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                sum += node->val;
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(sum / size); // 将每一层均值放进结果集
        }
        return result;
    }
};


429.N叉树的层序遍历

别被什么用null分割给唬住,看node 的结构,以前是两根左右指针,现在是一个vector<Node*>容器而已

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        queue<Node*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            for (int i = 0; i < size; i++) {
                Node* node = que.front();
                que.pop();
                vec.push_back(node->val);
                for (int i = 0; i < node->children.size(); i++) { // 将节点孩子加入队列
                    if (node->children[i]) que.push(node->children[i]);
                }
            }
            result.push_back(vec);
        }
        return result;

    }
};

515.在每个树行中找最大值

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<int> result;
        while (!que.empty()) {
            int size = que.size();
            int maxValue = INT_MIN; // 取每一层的最大值
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                maxValue = node->val > maxValue ? node->val : maxValue;
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(maxValue); // 把最大值放进数组
        }
        return result;
    }
};

116.填充每个节点的下一个右侧节点指针

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr) return root;
        queue<Node*> que;
        if(root->left) que.push(root->left);
        if(root->right) que.push(root->right);
        while(!que.empty()){
            int size = que.size();
            for(int i = 1; i < size; ++i){
                Node* cur1 = que.front(); //左
                que.pop();
                Node* cur2 = que.front(); //右
                cur1->next = cur2;
                if(cur1->left) que.push(cur1->left);
                if(cur1->right) que.push(cur1->right);
                if(i == size-1){
                    que.pop();
                    if(cur2->left) que.push(cur2->left);
                    if(cur2->right) que.push(cur2->right);
                } 
                
            }
        }
        return root;
    }
};

117.填充每个节点的下一个右侧节点指针II

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if(root == NULL) return root;
        queue<Node*> que;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            Node* pre;
            Node* cur;
            for(int i = 0; i < size; ++i){
                if(i == 0){
                    pre = que.front();
                    que.pop();
                    cur = pre;
                }else{
                    cur = que.front();
                    que.pop();
                    pre->next = cur;
                    pre = cur;
                }
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
        }
        return root;
    }
};

104.二叉树的最大深度

/**
 * 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:
    int maxDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        int depth = 0;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            for(int i = 0; i < size; ++i){
                TreeNode* cur = que.front();
                que.pop();
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
            depth++;
        }
        return depth;
    }
};

111.二叉树的最小深度

/**
 * 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:
    int minDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        int depth = 0;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            depth++;
            for(int i = 0; i < size; ++i){
                TreeNode* cur = que.front();
                que.pop();
                if(cur->left == nullptr && cur->right == nullptr) return depth;
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);

            }
        }
        return depth;
    }
};

226.翻转二叉树

递归的时候除了中序都可以(中序会让部分节点反转两次)
递归法:

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        swap(root->left, root->right);  // 中
        invertTree(root->left);         // 左
        invertTree(root->right);        // 右
        return root;
    }
};

深度迭代法(stack)

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode* node = st.top();              // 中
            st.pop();
            swap(node->left, node->right);
            if(node->right) st.push(node->right);   // 右
            if(node->left) st.push(node->left);     // 左
        }
        return root;
    }
};

101. 对称二叉树

思路:
1、递归
本题遍历只能是“后序遍历”,因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。
正是因为要遍历两棵树而且要比较内侧和外侧节点,所以准确的来说是一个树的遍历顺序是左右中,一个树的遍历顺序是右左中。
在终止条件中,首先看两个中节点是不是相同,如果中节点都不相同就没必要往下看,然后才是他们对应子树,只有子树相同,中节点这里才能返回true。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(root->left,root->right);
    }
    bool compare(TreeNode* left, TreeNode* right){
        if(left == nullptr && right != nullptr) return false;
        else if(left != nullptr && right == nullptr) return false;
        else if(left == nullptr && right == nullptr) return true;
        else if(left->val != right->val) return false;

        bool isleft = compare(left->left,right->right);
        bool isright = compare(left->right, right->left);
        return isleft && isright;
    }
};

2、层序遍历,放进队列中,两两取出比较即可

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == nullptr) return true;
        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 == nullptr && right != nullptr) return false;
            else if(left != nullptr && right == nullptr) return false;
            else if(left == nullptr && right == nullptr) continue;
            else if(left->val != right->val) return false;

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

3、深度遍历,使用栈
把队列直接换成栈就可以

104.二叉树的最大深度

在层序遍历中,使用的队列。现在使用递归法
本题可以使用前序(中左右),也可以使用后序遍历(左右中),使用前序求的就是深度,使用后序求的是高度。

二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数或者节点数(取决于深度从0开始还是从1开始)
二叉树节点的高度: 指从该节点到叶子节点的最长简单路径边的条数后者节点数(取决于高度从0开始还是从1开始)

1、而根节点的高度就是二叉树的最大深度,所以本题中我们通过后序求的根节点高度来求的二叉树最大深度

class Solution {
public:
    int maxDepth(TreeNode* root) {
        return maxdepth(root);
    }
    int maxdepth(TreeNode* cur){
        if(cur == nullptr) return 0;
        int depth ;
        int leftdepth = maxdepth(cur->left);
        int rightdepth = maxdepth(cur->right);
        depth = max(leftdepth,rightdepth);
        return depth+1; //depth记录的是当前中节点左右两节点的高度。返回的时候要加上中节点自身的高度,所以返回depth+1
    }
};

2、真正求深度的逻辑 前序遍历

class Solution {
public:
    int result;
    int maxDepth(TreeNode* root) {
        if(root == nullptr) return 0;
        result = 0;
        maxdepth(root,1);
        return result;
    }
    void maxdepth(TreeNode* cur,int depth){
        result = depth > result ? depth : result;
        if(cur->left == nullptr && cur->right == nullptr) return;
        
        if(cur->left){
            depth++;
            maxdepth(cur->left,depth);
            depth--;
        }
        if(cur->right){
            depth++;
            maxdepth(cur->right,depth);
            depth--;
        }
    }
};

111 二叉树的最小深度

前序遍历:

class Solution {
private:
    int result;
    void getdepth(TreeNode* node, int depth) {
        if (node->left == NULL && node->right == NULL) {
            result = min(depth, result);  
            return;
        }
        // 中 只不过中没有处理的逻辑
        if (node->left) { // 左
            getdepth(node->left, depth + 1);
        }
        if (node->right) { // 右
            getdepth(node->right, depth + 1);
        }
        return ;
    }

public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        result = INT_MAX;
        getdepth(root, 1);
        return result;
    }
};

后序遍历(很不熟)

class Solution {
public:
    int getDepth(TreeNode* node) {
        if (node == NULL) return 0;
        int leftDepth = getDepth(node->left);           // 左
        int rightDepth = getDepth(node->right);         // 右
                                                        // 中
        // 当一个左子树为空,右不为空,这时并不是最低点
        if (node->left == NULL && node->right != NULL) { 
            return 1 + rightDepth;
        }   
        // 当一个右子树为空,左不为空,这时并不是最低点
        if (node->left != NULL && node->right == NULL) { 
            return 1 + leftDepth;
        }
        int result = 1 + min(leftDepth, rightDepth);
        return result;
    }

    int minDepth(TreeNode* root) {
        return getDepth(root);
    }
};

222.完全二叉树的节点个数

class Solution {
public:
    int countNodes(TreeNode* root) {
        int leftcount = 0;
        int rightcount = 0;

        if(root == nullptr) return 0;
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        while(left){
            leftcount++;
            left = left->left;
        }
        while(right){
            rightcount++;
            right = right->right;
        }
        if(leftcount == rightcount){
            return (2<<leftcount) - 1;
        }

        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/9989.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

进来拿!最近疯传的154页微软 GPT-4早期实验报告:探究 AGI进化之路(全中文版)

这应该是&#xff0c;最近一段时间以来&#xff0c;关于 ChatGPT4.0剖析最全面的一份报告。 看懂10%&#xff0c;能帮我们对 ChatGPT 的认识&#xff0c;有一个质的跃升&#xff1b; 看懂50%&#xff0c;你将是分享 ChatGPT 知识领域最顶尖的那一拨人。 这份报告证明了 GPT-4…

若依数据隔离 ${params.dataScope} 替换 优化为sql 替换

若依数据隔离 ${params.dataScope} 替换 优化为sql 替换 安全问题:有风险的SQL查询&#xff1a;MyBatis解决 若依框架的数据隔离是通过 ${params.dataScope} 实现的 但是在代码安全扫描的时候$ 符会提示有风险的SQL查询&#xff1a;MyBatis 所以我们这里需要进行优化参考: M…

5分钟学会Ribbon负载均衡

文章目录一、Ribbon1.1 Ribbon的负载均衡流程&#xff1a;1.2 负载均衡策略1.2.1 内置的负载均衡策略1.2.2 如何修改负载均衡1.3 加载方式一、Ribbon 1.1 Ribbon的负载均衡流程&#xff1a; 获取可用的服务列表&#xff1a;客户端在进行服务调用之前&#xff0c;首先需要获取可…

如何基于ChatGPT+Avatar搭建24小时无人直播间

0 前言 最近朋友圈以及身边很多朋友都在研究GPT开发&#xff0c;做了各种各样的小工具小Demo&#xff0c;AI工具用起来是真的香&#xff01;在他们的影响下&#xff0c;我也继续捣鼓GPT Demo&#xff0c;希望更多的开发者加入一起多多交流。 上一篇结合即时通 IM SDK捣鼓了一个…

SpringAOP入门基础银行转账实例(进阶版)------------事务处理

SpringAOP入门基础银行转账实例**&#xff08;进阶版&#xff09;**------------事务处理 由上一节讲述的通过Connection和QueryRunner对事务进行的处理(详情可以去我之前写的博客文章&#xff1a;https://blog.csdn.net/m0_56245143/article/details/130069160?spm1001.2014…

VMware vSphere 8.0c - 企业级工作负载平台

ESXi 8.0.0 & vCenter Server 8.0.0 GA (General Availability) 请访问原文链接&#xff1a;https://sysin.org/blog/vmware-vsphere-8/&#xff0c;查看最新版。原创作品&#xff0c;转载请保留出处。 作者主页&#xff1a;sysin.org 2023-03-30, VMware vSphere 8.0c 发…

静态库与动态库

库是已经写好的、成熟的、可复用的代码。在我们的开发的应用中经常有一些公共代码是需要反复使用的&#xff0c;就把这些代码编译为库文件。库可以简单看成一组目标文件的集合&#xff0c;将这些目标文件经过压缩打包之后形成的一个可执行代码的二进制文件。库有两种&#xff1…

Ubuntu硬盘分区、挂载

文章目录1、使用命令查看硬盘情况2、分区3、格式化分区4、挂载手动挂载自动挂载1、使用命令查看硬盘情况 sudo fdisk -l 可以看到这里有个未分区的4T硬盘 如&#xff1a;sdb 这样的是硬盘 sdb1 sdb2 这样的是分区&#xff0c;现在还没分区 2、分区 sudo parted /dev/sdb (s…

一切都是命中注定的!

“光锥之内就是命运”&#xff0c;这是刘慈欣的《三体黑暗森林》里一句话&#xff0c;如果我们看到一件事情正在发生&#xff0c;那么它早在过去无论是几秒前还是几千年前&#xff0c;就已经发生了&#xff0c;我们无法改变这个命运。 孔明叹曰&#xff1a;“谋事在人&#xf…

树莓派通过网线连接笔记本实现笔记本电脑Wifi的网络共享

基于windows电脑连接树莓派进行设置&#xff1a;通过通过一根网线&#xff0c;连接树莓派和电脑&#xff0c;使电脑和树莓派构成一个局域网&#xff0c;然后树莓派接收来自笔记本电脑wifi网络的共享网络。操作方法类似台式机通过网线共享笔记本电脑无线网络的步骤 1、 保证笔记…

总结816

学习目标&#xff1a; 4月&#xff08;复习完高数18讲内容&#xff0c;背诵21篇短文&#xff0c;熟词僻义300词基础词&#xff09; 学习内容&#xff1a; 高等数学&#xff1a;一元积分&#xff0c;算是彻底过一遍了&#xff0c;但还是需要再回顾一遍。今日一道变限积分求导出…

简单的单目测距实验

一、原理 简单的单目测距方法&#xff0c;假设相机平面和物体平面平行&#xff0c;相机正对着物体表面拍摄&#xff0c;则可以利用相似三角形法。 用相似三角形计算物体或者目标到相机的距离&#xff0c;将使用相似三角形来计算相机到一个已知的物体或者目标的距离。 假设有…

执行数学的运算

数学是计算机编程的重要能力。遗憾的是&#xff0c;对shell脚本来说&#xff0c;这个处理过程比较麻烦。在shell脚本中两种途径来进行数学运算。 expr命令 最开始&#xff0c;Bourne shell提供了一个特别的命令用来处理数学表达式。expr命令允许在命令行上处理数学数学表达式。…

算法学习day59

算法学习day591.力扣503.下一个更大元素II1.1 题目描述1.2 分析1.3代码2.力扣42. 接雨水2.1 题目描述2.2 分析2.3 代码3.参考资料1.力扣503.下一个更大元素II 1.1 题目描述 题目描述&#xff1a; 给定一个循环数组&#xff08;最后一个元素的下一个元素是数组的第一个元素&a…

【Java 并发编程】一文了解线程间有哪些通信方式?

一文了解线程间有哪些通信方式&#xff1f;1. synchronized 内置锁2. volatile 关键字3. 等待/通知机制3.1 等待wait()wait(long)wait(long, int)等待方需遵循如下原则3.2 通知notify()notifyAll()通知方需遵循如下原则notify() 和 notifyAll() 应该用谁&#xff1f;4. 管道输入…

BusterNet网络Python模型实现学习笔记一

实在是无力吐槽了&#xff0c;心力交瘁。作者Github仓库给了错误的 USCISI-CMFD-Small 数据集。自己捣鼓了半天&#xff0c;发现原来是压缩之后数据集&#xff0c;也就是 LMDB 文件格式出错了。实在是误人子弟&#xff0c;自己已经气急败坏了现在… 但是既然论文都花那么长时间…

数据分析之Pandas 基础入门

一、初始Pandas pandas 是数据分析三大件之一&#xff0c;是Python的核心分析库&#xff0c;它提供了快捷、灵活、明确的数据结构&#xff0c;它能够简单、直观、快速的处理各种类型的数据结构。 pandas 支持的数据结构如下&#xff1a; SQL 或Excel 类似的数据有序或无序的…

【学习笔记】unity脚本学习(三)(向量 Vector3)

目录向量复习高中向量基础【数学】向量的四则运算、点积、叉积、正交基叉乘公式叉乘运算定理向量、坐标系点积叉积Vector3 三维向量静态变量变量变量normalized 与 Normalize() 方法静态方法ClampMagnitudeCrossDistanceDotMoveTowards其他变换类似Lerp 在两个点之间进行线性插…

实现一个简单但有趣的AR效果(Web)

有人说:一个人从1岁活到80岁很平凡,但如果从80岁倒着活,那么一半以上的人都可能不凡。 生活没有捷径,我们踩过的坑都成为了生活的经验,这些经验越早知道,你要走的弯路就会越少。

MySQL 库操作

目录 创建数据库 语法 案例 字符集和校验规则&#xff08;建数据库/建表用&#xff09; 查看系统默认字符集以及校验规则 db.opt 更改 查看数据库支持的字符集 查看数据库支持的字符集校验规则 校验规则对数据库的影响 排升序 操纵数据库 查看数据库 显示创建语…
最新文章