当前位置： 首页 > article >正文

代码随想录day12

article 2025/2/24 10:01:07

144.二叉树的前序遍历

//明确递归的函数，结束边界，单层逻辑

    void traversal(TreeNode* node, vector<int>& list){
        if(node == nullptr){
            return;
        }
        list.push_back(node->val);
        traversal(node->left, list);
        traversal(node->right, list);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }

//迭代法

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> traversal;
        if(root == nullptr){
            return result;
        }
        traversal.push(root);
        while(!traversal.empty()){
            TreeNode* cur = traversal.top();
            result.push_back(cur->val);
            traversal.pop();
            if(cur->right) traversal.push(cur->right);
            if(cur->left) traversal.push(cur->left);
        }
        return result;
    }

//统一迭代法

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<pair<TreeNode*, bool>> st;
        if(root == nullptr) return result;
        st.push(make_pair(root, false));
        while(!st.empty()){
            auto node = st.top();
            st.pop();
            if(node.second){
                result.push_back(node.first->val);
            } else {
                
                if(node.first->right) st.push(make_pair(node.first->right, false));
                if(node.first->left) st.push(make_pair(node.first->left, false));
                st.push(make_pair(node.first, true));
            }
        }
        return result;
    }

145.二叉树的后序遍历

    void traversal(TreeNode* node, vector<int>& list){
        if(node == nullptr){
            return;
        }
        traversal(node->left, list);
        traversal(node->right, list);
        list.push_back(node->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }

//迭代法 左右中-》中右左-〉中左右

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> traversal;
        if(root == nullptr) return result;
        traversal.push(root);
        while(!traversal.empty()){
            TreeNode* cur = traversal.top();
            result.push_back(cur->val);
            traversal.pop();
            if(cur->left) traversal.push(cur->left);
            if(cur->right) traversal.push(cur->right);
        }
        reverse(result.begin(), result.end());
        return result;
    }

//统一迭代法

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<pair<TreeNode*,bool>> st;
        if(root == nullptr) return result;
        st.push(make_pair(root, false));
        while(!st.empty()){
            auto node = st.top();
            st.pop();
            if(node.second){
                result.push_back(node.first->val);
            }else{
                st.push(make_pair(node.first, true));
                if(node.first->right) st.push(make_pair(node.first->right, false));
                if(node.first->left) st.push(make_pair(node.first->left, false));
            }
        }
        return result;
    }

94.二叉树的中序遍历

    void traversal(TreeNode* node, vector<int>& list){
        if(node == nullptr){
            return;
        }
        traversal(node->left, list);
        list.push_back(node->val);
        traversal(node->right, list);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }

//迭代法，需理解左中右无法直接处理

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if(root == nullptr) return result;
        TreeNode* cur = root;
        while(cur != nullptr || !st.empty()){
            if(cur != nullptr){
                st.push(cur);
                cur = cur->left;
            }else{
                cur = st.top();
                result.push_back(cur->val);
                st.pop();
                cur = cur->right;
            }
        }
        return result;
    }

//统一迭代法

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<pair<TreeNode*, bool>> st;
        if(root == nullptr) return result;
        st.push(make_pair(root, false));
        while(!st.empty()){
            auto node = st.top();
            st.pop();
            if(node.second) {
                result.push_back(node.first->val);
            }else{
                if(node.first->right) st.push(make_pair(node.first->right, false));
                st.push(make_pair(node.first, true));
                if(node.first->left) st.push(make_pair(node.first->left, false));
            }
        }
        return result;
    }

102.二叉树的层序遍历

//广度优先遍历，使用queue的迭代法

    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> qe;
        if(root == nullptr) return result;
        qe.push(root);
        while(!qe.empty()){
            int sz = qe.size();
            vector<int> tmp;
            for(int i = 0; i < sz; i++){
                auto node = qe.front();
                qe.pop();
                tmp.push_back(node->val);
                if(node->left) qe.push(node->left);
                if(node->right) qe.push(node->right);
            }
            result.push_back(tmp);
        }
        return result;
    }

//递归法

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

107.二叉树的层序遍历II

上题结果reverse即可。

199.二叉树的右视图

//保存层序遍历中每层的最后一位

    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        queue<TreeNode*> qe;
        if(root == nullptr) return result;
        qe.push(root);
        while(!qe.empty()){
            int sz = qe.size();
            vector<int> tmp;
            for(int i = 0; i < sz; i++){
                TreeNode* node = qe.front();
                qe.pop();
                tmp.push_back(node->val);
                if(node->left){
                    qe.push(node->left);
                }
                if(node->right) {
                    qe.push(node->right);
                }
            }
            result.push_back(tmp[sz-1]);
        }
        return result;
    }

637.二叉树的层平均值

//计算每层的总和然后除以size即可

    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> result;
        queue<TreeNode*> qe;
        if(root == nullptr) return result;
        qe.push(root);
        while(!qe.empty()){
            int sz = qe.size();
            double tmp = 0;
            for(int i = 0; i < sz; i++){
                TreeNode* node = qe.front();
                qe.pop();
                tmp += node->val;
                if(node->left) qe.push(node->left);
                if(node->right) qe.push(node->right);
            }
            double x = tmp/sz;
            result.push_back(x);
        }
        return result;
    }

429.N叉树的层序遍历

    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> result;
        queue<Node*> qe;
        if(root == nullptr) return result;
        qe.push(root);
        while(!qe.empty()){
            int sz = qe.size();
            vector<int> tmp;
            for(int i = 0; i < sz; i++){
                Node* nd = qe.front();
                qe.pop();
                tmp.push_back(nd->val);
                int cd_sz = nd->children.size();
                for(int j = 0; j < cd_sz; j++){
                    if(nd->children[j]){
                        qe.push(nd->children[j]);
                    }
                }
            }
            result.push_back(tmp);
        }
        return result;
    }

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

    vector<int> largestValues(TreeNode* root) {
        vector<int> result;
        queue<TreeNode*> qe;
        if(root == nullptr) return result;
        qe.push(root);
        while(!qe.empty()){
            int sz = qe.size();
            int tmp = qe.front()->val;
            for(int i = 0; i < sz; i++){
                TreeNode* node = qe.front();
                qe.pop();
                if(node->val > tmp) tmp = node->val;
                if(node->left) qe.push(node->left);
                if(node->right) qe.push(node->right);
            }
            result.push_back(tmp);
        } 
        return result;
    }

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

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

    Node* connect(Node* root) {
        queue<Node*> qe;
        if(root == nullptr) return root;
        qe.push(root);
        while(!qe.empty()){
            int sz = qe.size();
            for(int i = 0; i < sz; i++){
                Node* nd = qe.front();
                qe.pop();
                if(i == sz - 1){
                    nd->next = nullptr;
                }
                else{
                    nd->next = qe.front();
                }
                if(nd->left) qe.push(nd->left);
                if(nd->right) qe.push(nd->right); 
            }
        }
        return root;
    }

104.二叉树的最大深度

    int maxDepth(TreeNode* root) {
        int result = 0;
        queue<TreeNode*> qe;
        if(root == nullptr) return result;
        qe.push(root);
        while(!qe.empty()){
            int sz = qe.size();
            for(int i = 0; i < sz; i++){
                TreeNode* nd = qe.front();
                qe.pop();
                if(nd->left) qe.push(nd->left);
                if(nd->right) qe.push(nd->right);
            }
            result += 1;
        }
        return result;
    }

111.二叉树的最小深度

    int minDepth(TreeNode* root) {
        int result = 0;
        queue<TreeNode*> qe;
        if(root == nullptr) return result;
        qe.push(root);
        while(!qe.empty()){
            int sz = qe.size();
            result += 1;
            for(int i = 0; i < sz; i++){
                TreeNode* nd = qe.front();
                qe.pop();
                if(!nd->left && !nd->right) return result;
                if(nd->left) qe.push(nd->left);
                if(nd->right) qe.push(nd->right);
            }
            
        }
        return result;
    }

最近几天有点事，拖了进度，后序需坚持跟上，加油


http://www.kler.cn/a/551288.html

相关文章：

  • 【第1章：深度学习概览——1.6 深度学习框架简介与选择建议】
  • DeepSeek-R1本地部署详细指南！(Ollama+Chatbox AI+Open WebUI)
  • 开源赋能，智造未来：Odoo+工业物联网，解锁智能工厂新范式——以真实案例解读制造业数字化转型的降本增效密码
  • DeepSeek教unity------MessagePack-04
  • 零基础学QT、C++（一）安装QT
  • 深入解析 Vue 3 编译宏：揭开 `＜script setup＞` 的魔法面纱
  • 力扣-二叉树-513 找二叉树左下角的值
  • python学习笔记，python处理 Excel、Word、PPT 以及邮件自动化办公
  • Qt creater 出现“启动程序失败，路径或者权限错误”解决方法
  • gozero实现数据库MySQL单例模式连接
  • Linux探秘坊-------8.进程详解
  • PyTorch入门实战：从零搭建你的第一个神经网络
  • （尚硅谷 Java 学习 B 站大学版）Day17 多态练习
  • 001-监控你的文件-FSWatch-C++开源库108杰
  • 以用户为中心，汽车 HMI 界面设计的创新之道
  • MySQL智障离谱问题，删了库确还存在、也不能再创建同名库
  • 【Pytorch 库】自定义数据集相关的类
  • 基于Unity引擎的网络通信架构深度解析——以NetworkConnectionController为例
  • 聊一聊vue如何实现角色权限的控制的
  • 【16届蓝桥杯寒假刷题营】第2期DAY1I