力扣hot100--二叉树

embedded/2024/10/15 22:00:41/

二叉树

1. 94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

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

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

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

// 二叉树的遍历
class Solution {
public:
    vector<int> result; // 用来存储中序遍历的结果的向量

    // 中序遍历的递归函数
    void inorder(TreeNode* root){
        if(!root) return; // 如果节点为空，直接返回

        inorder(root->left); // 递归遍历左子树
        result.push_back(root->val); // 将当前节点的值加入结果向量
        inorder(root->right); // 递归遍历右子树
    }

    // 主函数，返回中序遍历的结果
    vector<int> inorderTraversal(TreeNode* root) {
        inorder(root); // 调用中序遍历的递归函数
        return result; // 返回结果向量
    }
};

解释： 

  • 从根节点开始，先访问左子树，然后访问根节点，最后访问右子树。
  • 对于当前的二叉树：
    • 根节点为 1，先访问左子树，但是左子树为空，因此直接访问根节点 1，将 1 加入结果数组。
    • 然后访问右子树，右子树是节点 2。
    • 对于节点 2，先访问左子树，即节点 3。访问节点 3，将 3 加入结果数组。
    • 然后访问根节点 2，将 2 加入结果数组。

2. 98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

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

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

  • 树中节点数目范围在[1, 104] 内
  • -231 <= Node.val <= 231 - 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 isBSTHelper(TreeNode* root, int minVal, int maxVal) {
        // 如果节点为空，返回true
        if (!root) return true;
        
        // 检查当前节点值是否在允许的范围内
        if (root->val <= minVal || root->val >= maxVal) {
            return false;
        }
        
        // 递归检查左子树和右子树，更新范围
        return isBSTHelper(root->left, minVal, root->val) &&
               isBSTHelper(root->right, root->val, maxVal);
    }

    // 主函数，判断给定的二叉树是否是有效的二叉搜索树
    bool isValidBST(TreeNode* root) {
        // 初始时，最小值为INT_MIN，最大值为INT_MAX
        return isBSTHelper(root, INT_MIN, INT_MAX);
    }
};

3. 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

/**
 * 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 recursive(TreeNode* left, TreeNode* right) {
        // 如果两个子树都为空，则它们对称，返回true
        if (!left && !right) return true;
        
        // 如果一个子树为空，而另一个子树不为空，则不对称，返回false
        else if (left && !right) return false;
        else if (!left && right) return false;

        // 如果两个子树的根节点值不相等，则不对称，返回false
        if (left->val != right->val) return false;
        
        // 递归检查左子树的左子节点与右子树的右子节点是否对称，以及
        // 左子树的右子节点与右子树的左子节点是否对称
        bool flag = recursive(left->left, right->right);
        bool flag1 = recursive(left->right, right->left);

        // 只有当左右两侧子树都对称时，返回true；否则返回false
        return flag && flag1;
    }

    // 检查整个树是否是对称的
    bool isSymmetric(TreeNode* root) {
        // 如果根节点为空，树是对称的，返回true
        if (!root) return true;

        // 调用递归函数，检查根节点的左子树和右子树是否是镜像对称的
        return recursive(root->left, root->right);
    }
};

4.102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

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

// 二叉树的遍历
/**
 * 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>> result; // 存储每一层节点值的结果

    // 层次遍历二叉树
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (!root) return {}; // 如果根节点为空，返回空的二维向量

        queue<TreeNode*> q; // 创建一个队列用于存储待遍历的节点
        q.push(root); // 将根节点入队

        // 当队列不为空时，继续遍历
        while (!q.empty()) {
            int n = q.size(); // 当前层的节点数量
            vector<int> v1; // 用于存储当前层的节点值

            // 遍历当前层的所有节点
            for (int i{}; i < n; ++i) {
                TreeNode* node = q.front(); // 获取队列的前端节点
                q.pop(); // 将该节点出队

                v1.emplace_back(node->val); // 将该节点的值添加到当前层结果中

                // 将左右子节点入队（如果存在）
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }

            result.push_back(v1); // 将当前层的节点值存入结果中
        }
        return result; // 返回结果
    }
};

5. 104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2

提示：

  • 树中节点的数量在 [0, 104] 区间内。
  • -100 <= Node.val <= 100

/**
 * 定义二叉树节点的结构。
 * 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) {
        // 如果当前节点为空（基例），返回 0
        if (!root) return 0;  // 更正了原代码中的 {} 为 0

        // 递归计算左子树和右子树的深度
        // 返回两个深度的最大值加上当前节点的深度（1）
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

6.105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder 和 inorder 均 无重复 元素
  • inorder 均出现在 preorder
  • preorder 保证 为二叉树的前序遍历序列
  • inorder 保证 为二叉树的中序遍历序列

// 树的遍历
/**
 * 定义二叉树节点的结构。
 * 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:
    // 辅助函数：递归构造二叉树
    TreeNode* recursive(vector<int>& inorder, vector<int>& preorder) {
        // 递归的终止条件：如果前序遍历的数组为空，返回空节点
        if (preorder.size() == 0) return nullptr;

        // 前序遍历的第一个元素是根节点
        TreeNode* root = new TreeNode(preorder[0]);

        // 在中序遍历中找到根节点的位置，根节点左边的是左子树，右边的是右子树
        int index = 0;
        for (int i = 0; i < inorder.size(); ++i) {
            if (inorder[i] == preorder[0]) {
                index = i;  // 找到根节点在中序遍历中的位置
                break;
            }
        }

        // 根据中序遍历分割出左子树和右子树的节点范围
        vector<int> leftInorder(inorder.begin(), inorder.begin() + index);  // 左子树的中序遍历
        vector<int> rightInorder(inorder.begin() + index + 1, inorder.end());  // 右子树的中序遍历

        // 根据前序遍历分割出左子树和右子树的节点范围
        vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + 1 + leftInorder.size());  // 左子树的前序遍历
        vector<int> rightPreorder(preorder.begin() + 1 + leftInorder.size(), preorder.end());  // 右子树的前序遍历

        // 递归构建左子树和右子树
        root->left = recursive(leftInorder, leftPreorder);  // 构建左子树
        root->right = recursive(rightInorder, rightPreorder);  // 构建右子树

        return root;  // 返回当前的根节点
    }

    // 主函数：根据前序遍历和中序遍历构造二叉树
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 如果前序遍历或中序遍历为空，直接返回空树
        if (preorder.size() == 0 || inorder.size() == 0) return nullptr;

        // 调用辅助函数进行递归构造
        return recursive(inorder, preorder);
    }
};

解释： 

vector<int> leftInorder(inorder.begin(), inorder.begin() + index) 的范围在数学上可以表示为 [0,index)[0, \text{index})[0,index)。

class Solution {
private:
    unordered_map<int, int> inorderMap; // 存储中序遍历的值到索引的映射
    int preorderIndex = 0; // 前序遍历的当前索引

    // 递归帮助函数，用于构建树
    TreeNode* buildTreeHelper(vector<int>& preorder, int left, int right) {
        if (right < left) return nullptr; // 基本情况：没有节点可构建，返回 nullptr

        // 获取当前根节点的值并创建 TreeNode
        int rootVal = preorder[preorderIndex++];
        TreeNode* root = new TreeNode(rootVal);
        
        // 获取当前根值在中序数组中的索引
        int inorderIndex = inorderMap[rootVal];

        // 递归构建左子树和右子树
        root->left = buildTreeHelper(preorder, left, inorderIndex - 1); // 左子树范围
        root->right = buildTreeHelper(preorder, inorderIndex + 1, right); // 右子树范围
        
        return root; // 返回构建的子树
    }

public:
    // 主函数，从前序和中序遍历构建二叉树
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        preorderIndex = 0; // 重置前序遍历索引
        // 填充中序数组的值到索引的映射
        for (int i = 0; i < inorder.size(); i++) {
            inorderMap[inorder[i]] = i; // 记录每个值在中序数组中的索引
        }
        // 开始递归构建树
        return buildTreeHelper(preorder, 0, inorder.size() - 1);
    }
};

解释：

  • unordered_map 用于存储中序遍历中的值与其对应的索引，以便快速查找。
  • preorderIndex 用于追踪前序遍历中当前的索引，以获取根节点的值。
  • buildTreeHelper 是一个递归函数，用于构建树。通过指定的范围（left 和 right）构建子树，并返回构建的节点。
  • 基本情况：如果当前的范围没有元素（right < left），则返回 nullptr。
  • 树的构建过程：
    • 创建根节点。
    • 查找根节点在中序数组中的位置。
    • 递归构建左子树和右子树。

http://www.ppmy.cn/embedded/128095.html

相关文章

【银行科技岗】相关考试知识点总结及部分考题

【银行科技岗】相关考试知识点总结及部分考题

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 一、**网络与安全**二、**软件开发与设计**三、**数据库与数据管理**四、**编程与系统**五、**计算机硬件与性能**六、**大数据与人工智能**七、**系统与应用**相关…
阅读更多...
pdf阅读软件有哪些？5个软件帮助你快速进行pdf阅读

pdf阅读软件有哪些？5个软件帮助你快速进行pdf阅读

pdf阅读软件有哪些&#xff1f;5个软件帮助你快速进行pdf阅读 如果你正在寻找优秀的PDF阅读软件&#xff0c;以下推荐的5款软件能够帮助你快速、轻松地阅读和管理PDF文件。这些工具各具特色&#xff0c;适用于不同的使用需求&#xff0c;无论是注释、签名、还是管理大文件&…
阅读更多...
基于Spring Boot REST API设计指南

基于Spring Boot REST API设计指南

在构建现代Web应用程序时&#xff0c;RESTful API已成为一种标准&#xff0c;使得不同的应用程序能够通过HTTP协议进行通信&#xff0c;实现资源的创建、读取、更新和删除等操作。Spring Boot作为一个功能强大的框架&#xff0c;能够轻松创建RESTful API。本文将详细介绍如何在…
阅读更多...
非js脚本打开浏览器窗口的关闭解决方案

非js脚本打开浏览器窗口的关闭解决方案

js脚本打开方式浏览器窗口 关闭方式&#xff1a; window.close() 非js脚本打开方式浏览器页面 只是前端开发者会惊奇的发现&#xff0c;使用window.close() API,并不能每次成功关闭浏览器窗口&#xff0c;打开控制台发现会有一条警告信息 错误分析&#xff1a; 为什么浏览…
阅读更多...
企业在隔离网环境下如何进行安全又稳定的跨网文件交换？

企业在隔离网环境下如何进行安全又稳定的跨网文件交换？

在数字化时代&#xff0c;企业的数据流通如同血液一般重要。然而&#xff0c;当企业内部实施了隔离网环境&#xff0c;跨网文件交换就成了一个棘手的问题。今天我们将探讨在隔离网环境下&#xff0c;企业面临的跨网文件交换挑战&#xff0c;以及如何通过合规的跨网文件交换系统…
阅读更多...
目录类QDir

目录类QDir

Qt使用"/"来作为通用的目录分隔符&#xff0c;所以表示文件路径的字符串中我们最好用"/" 使用"/"&#xff0c;Qt会自动的转换你的路径来匹配你当前使用的操作系统 常用静态方法 获取当前项目所在的路径 [static] QString QDir::currentPath(…
阅读更多...
YoloDotNet 图像目标检测功能详解

YoloDotNet 图像目标检测功能详解

文章目录 一、模型选择与下载二、环境配置与库引用三、图像读取与预处理四、模型加载与初始化五、目标检测执行六、结果展示与分析一、模型选择与下载 在使用 YoloDotNet 进行图像目标检测时，首先需要选择合适的模型。Yolo 有多个版本，如 YoloV5、YoloV8 等，每个版本又有不同…
阅读更多...
《大规模语言模型从理论到实践》第一轮学习--Fine-tuning微调

《大规模语言模型从理论到实践》第一轮学习--Fine-tuning微调

第一轮学习目标&#xff1a;了解大模型理论体系 第二轮学习目标&#xff1a;进行具体实操进一步深入理解大模型 从大语言模型的训练过程来理解微调 大预言模型训练主要包含四个阶段&#xff1a;预训练、有监督微调、奖励建模、强化学习。 预训练&#xff08;Pretraining&…
阅读更多...
最新文章

Copyright @ 2022~2023