【数据结构与算法】LeetCode：二叉树

🕗 发布于 2024-10-04 09:50 leetcode c++

文章目录

二叉树

二叉树

前序遍历（Pre-order Traversal）、中序遍历（In-order Traversal）、后序遍历（Post-order Traversal）和层序遍历（Level-order Traversal）是四种常见的遍历树形结构的方法。四种遍历方法的主要区别在于它们访问节点的顺序不同。

前序遍历 首先访问根节点，然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然遵循前序遍历的规则。
中序遍历 首先遍历左子树，然后访问根节点，最后遍历右子树。在遍历左、右子树时，仍然遵循中序遍历的规则。
后序遍历 首先遍历左子树，然后遍历右子树，最后访问根节点。在遍历左、右子树时，仍然遵循后序遍历的规则。

前序、中序和后序遍历常用于对树形结构进行深度优先搜索（DFS）。通常使用递归或栈迭代来实现。

层序遍历 从根节点开始，首先访问第一层节点，然后逐层向下访问。在同一层中，按照从左到右的顺序访问节点。

层序遍历常用于对树形结构进行广度优先搜索（BFS），通常使用队列迭代来实现。

前序遍历

二叉树的前序遍历

递归：

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == nullptr) return; // 递归终止条件
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

迭代：

class Solution {
public:
    vector<int>preorderTraversal(TreeNode* root){
        stack<TreeNode*> st;
        vector<int> result;
        if(root == nullptr) return result;
        st.push(root);
        while(!st.empty()){
            TreeNode* node = st.top();  // 根节点出栈
            st.pop();
            result.push_back(node->val);
            if(node->right) st.push(node->right); // 右子树入栈，
            if(node->left) st.push(node->left);  // 左子树入栈
        }
        return result;
    }
};

二叉树展开为链表（Hot 100）

二叉树展开为链表

class Solution {
public:
    void flatten(TreeNode* root) {
        vector<TreeNode*> node_list;
        // 前序遍历
        preorderTraversal(root, node_list); 
        // 连接
        for(int i = 1; i < node_list.size(); i++){
            TreeNode* pre = node_list[i - 1], *cur = node_list[i];
            pre->left = nullptr;
            pre->right = cur;
        }
    }
    void preorderTraversal(TreeNode* root, vector<TreeNode*> & node_list){
        if(root == nullptr) return;
        node_list.push_back(root);
        preorderTraversal(root->left, node_list);
        preorderTraversal(root->right, node_list);
    }
};

中序遍历

二叉树的中序遍历 (Hot 100)

二叉树的中序遍历
递归

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        traversal(cur->left, vec);  // 左
        vec.push_back(cur->val);    // 中
        traversal(cur->right, vec); // 右
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

迭代

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

验证二叉搜索树 (Hot 100)

验证二叉搜索树
二叉搜索树的中序遍历为递增序列

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> stack;
        long long inorder = (long long)INT_MIN - 1;
        TreeNode* cur = root;
        while (!stack.empty() || cur != nullptr) {
            while (cur != nullptr) {
                stack.push(cur);
                cur = cur -> left;
            }
            cur = stack.top();
            stack.pop();
            // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if (cur -> val <= inorder) {
                return false;
            }
            inorder = cur -> val;
            cur = cur -> right;
        }
        return true;
    }
};

二叉搜索树中第K小的元素 (Hot 100)

二叉搜索树中第K小的元素

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode *> stack;
        TreeNode* cur = root;
        while (cur != nullptr || stack.size() > 0) {
            while (cur != nullptr) {
                stack.push(cur);
                cur = cur->left;
            }
            cur = stack.top();
            stack.pop();
            --k;
            if (k == 0) {
                break;
            }
            cur = cur->right;
        }
        return cur->val;
    }
};

后序遍历

二叉树的后序遍历

二叉树的后序遍历
递归：

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == nullptr) return;
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
        vec.push_back(cur->val);    // 中
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

迭代：中右左遍历，然后reverse得到左右中

class Solution {
public:
    vector<int>postorderTraversal(TreeNode* root){
        stack<TreeNode*> st;
        vector<int> result;
        if(root==NULL) return result;
        st.push(root);
        while(!st.empty()){
            TreeNode* node = st.top();
            st.pop();
            result.push_back(node->val);
            if(node->left) st.push(node->left);
            if(node->right) st.push(node->right);
        }
        reverse(result.begin(), result.end());
      
        return result;

    }
};

层序遍历

二叉树的层序遍历（Hot 100）

二叉树的层序遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if(root != nullptr) 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);
        }
        return result;
    }
};

二叉树的最大深度

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == NULL) 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* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return depth;
    }
};

翻转二叉树（Hot 100）

翻转二叉树

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                swap(node->left, node->right); // 节点处理
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return root;
    }
};

二叉树的右视图（Hot 100）

二叉树的右视图

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<int> result;
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                // 将每一层的最后元素放入result数组中
                if (i == (size - 1)) result.push_back(node->val); 
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return result;
    }
};

二叉树的锯齿形层序遍历

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> res;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            vector<int> tmp;
            for(int i = que.size(); i > 0; i--) {
                TreeNode* node = que.front();
                que.pop();
                tmp.push_back(node->val);
                if (node->left != NULL) que.push(node->left);
                if (node->right != NULL) que.push(node->right);
            }
            if (res.size() % 2 == 1) reverse(tmp.begin(),tmp.end());
            res.push_back(tmp);
        }
        return res;
    }
};

原文地址：https://blog.csdn.net/weixin_44378835/article/details/138807866

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【机器学习】任务六：分类算法（支持向量机（SVM）在线性可分与不可分数据中的应用与可视化分析）
下一篇：【leetcode】169.多数元素

使用 C++ 实现卷积运算：从理论到实践的详细指南
卷积（Convolution）是信号处理、图像处理以及深度学习等领域中的核心操作。它广泛应用于图像滤波、特征提取和卷积神经网络（CNN）等方面。本文将从卷积运算的基本原理出发，详细介绍如何用 C++
阅读更多2024-10-04
MATLAB算法实战应用案例精讲-【人工智能】数据资产三次入表（概念篇）
数据资产入表就是将企业的数据资源以资产的形式纳入财务报表中进行管理和计量。其操作可以拆解为三步，第一步是入表形成原始资产，第二步是形成无形资产收入，第三步是形成存量资产。原始资产入表是指系统建设及数据
阅读更多2024-10-04
使用Python实现图形学的阴影贴图算法
从光源视角生成深度贴图：光源视角下的每个像素存储到光源的距离，这形成了一张深度图。从相机视角渲染场景：在渲染场景时，对每个像素进行深度测试，判断该像素是否在光源的阴影范围内。光照与阴影判断：如果某个点
阅读更多2024-10-04
【PyTorch】图像目标检测
按流程分为：one-stage和two-stage。
阅读更多2024-10-04
C++（string类的实现）
string类的实现
阅读更多2024-10-04
[含文档+PPT+源码等]精品基于Python实现的美术馆网站的设计与实现
基于Python实现的美术馆网站，其设计与实现背景主要源于以下几个方面的需求和发展趋势：随着文化娱乐活动的日益丰富，美术馆作为展示艺术作品、传播文化的重要场所，其管理和服务模式的创新对于提升公众的文化
阅读更多2024-10-04
Linux基础命令ps详解
ps（process status）命令用于报告当前正在运行的进程信息。它常用于监控和管理系统中的进程。以下是ps命令的常用参数及其详细解释与示例。
阅读更多2024-10-04
问：说说Java中基本数据类型长度及用法？
Java数据类型分基本和引用两类，基本类型包括byte、short、int、long、float、double、char和boolean，各类型占用内存不同。优化策略包括选合适类型、用位运算、避免包装
阅读更多2024-10-04
前端编程艺术（1）---HTML
HTML（HyperText Markup Language，超文本标记语言）是一种用于创建网页的标准标记语言。它描述了一个网站的结构骨架，使得浏览器能够展示具有特定格式的文本、链接、图片和其他内容。
阅读更多2024-10-04
MATLAB中qmr函数用法
但如果您随后会对经平衡处理的矩阵 B = R*P*A*C 进行因式分解，使用 equilibrate 还可以获得质量更好的预条件子矩阵。如果 qmr 无法在达到最大迭代次数后收敛或出于任何原因暂停，则
阅读更多2024-10-04