AI 助理
备案控制台
开发者社区 人工智能 文章 正文

[算法训练营] 二叉树专题(三)

2023-12-05 68
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： [算法训练营] 二叉树专题(三)

前言

本篇为二叉树专题的刷题题单，总共7道题，每道题都有对应的链接。

边听歌边刷题吧~

Yesterday

236. 二叉树的最近公共祖先

链接：236. 二叉树的最近公共祖先

解题思路

@代码随想录

卡哥讲的很清楚

  1. 求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式。
  2. 在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。
  3. 要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果。

AC代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==q || root==p || root==NULL)return root;
        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        TreeNode* right = lowestCommonAncestor(root->right,p,q);
        if(left!=NULL && right!=NULL)return root;
        if(left==NULL&&right!=NULL)return right;
        else if(left!=NULL&&right==NULL)return left;
        else return NULL;
    }
};

235. 二叉搜索树的最近公共祖先

链接：235. 二叉搜索树的最近公共祖先

解题思路

  • 更好的题解参考代码随想录，这里只记录我的理解
  • 方法一
  • 遍历整颗树，找它的最近公共祖先，就和236题一样
  • 方法二
  • 利用二叉搜索树的性质：从根开始，从上往下开始，找两个节点的公共根节点，只要这个节点的值在两个节点的值之间，这个节点就是这两个节点的最近公共根节点
  • 所以我们只需要找到这个节点就可以了，从上往下，如果这个值大于那两个节点的值就往左子树走
  • 否则往右子树走
  • 直到节点的值在两个节点值的中间即可返回节点

AC代码

方法一
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==p || root==q || root==NULL)return root;
        TreeNode* left=lowestCommonAncestor(root->left,p,q);
        TreeNode* right=lowestCommonAncestor(root->right,p,q);
        if(left!=NULL && right!=NULL)return root;
        if(left==NULL)return right;
        return left;
    }
};
方法二
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
//方法二
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL)return NULL;
        if(root->val > q->val && root->val > p->val){
            TreeNode* left= lowestCommonAncestor(root->left,p,q);
            if(left!=NULL)return left;
        }
        if(root->val < p->val && root->val < q->val){
            TreeNode* right= lowestCommonAncestor(root->right,p,q);
            if(right!=NULL)return right;
        }
        return root;
    }
};

701. 二叉搜索树中的插入操作

链接：

解题思路

  • 只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了。
  • 推荐题解@代码随想录

AC代码

/**
 * 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:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root==nullptr){
            TreeNode*node = new TreeNode(val);
            return node;
        }
        if(root->val > val)root->left=insertIntoBST(root->left,val);
        if(root->val < val)root->right=insertIntoBST(root->right,val);
        return root;
    }
};

450. 删除二叉搜索树中的节点

链接：450. 删除二叉搜索树中的节点

解题思路

  • 利用二叉搜索树的性质→该节点左边的值比该节点小，右边的值比该节点大
  • 其他的情况都比较简单，在代码中都注释了，这里只讲一下找到这个节点的时候，它的左右节点都不为空时
  • 在找到这个要求删除的节点的时候，可以把这个节点的左子树接到该节点右子树的最左边的节点，然后让该节点变为该节点的右节点即可
  • 如下图所示


AC代码

/**
/**
 * 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:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root==nullptr)return nullptr;
        if(root->val==key){
            if(root->left==nullptr&&root->right==nullptr){
                delete root;
                return nullptr;
            }else if(root->left==nullptr){
                auto resnode=root->right;
                delete root;
                return resnode;
            }else if(root->right==nullptr){
                auto resnode=root->left;
                delete root;
                return resnode;
            }else{
                TreeNode* cur=root->right;
                while(cur->left!=nullptr){
                    cur=cur->left;
                }
                cur->left=root->left;
                root=root->right;
                return root;
            }
        }
        if(root->val>key)root->left=deleteNode(root->left,key);
        if(root->val<key)root->right=deleteNode(root->right,key);
        return root;
    }
};

669. 修剪二叉搜索树

链接：669. 修剪二叉搜索树

解题思路

  • 题目要求修改二叉搜索树，使得所有节点的值在[low, high]中
  • 那么就需要遍历二叉树，当节点的值小于low时，这个节点的左子树就可以不用管，可以连同这个节点一起删除，只需要将右子树保留即可
  • 当节点的值大于high时，这个节点的右子树就可以不用管，可以连同这个节点一起删除，只需要将左子树保留即可

AC代码

/**
 * 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:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(root==nullptr)return root;
        if(root->val < low){
            TreeNode* right=trimBST(root->right,low,high);
            return right;
        }
        if(root->val > high){
            TreeNode* left=trimBST(root->left,low,high);
            return left;
        }
        root->left=trimBST(root->left,low,high);
        root->right=trimBST(root->right,low,high);
        return root;
    }
};

538. 把二叉搜索树转换为累加树

  1. 把二叉搜索树转换为累加树

解题思路

  • 题目要求的是让每个节点的值等于该树中所有大于等于该节点的值的和
  • 而且题目提供的是一棵二叉搜索树，它的中序遍历是单调递增的
  • 所以可以反向中序遍历，使用一个变量pre来保存这个节点之前的节点和
  • 后面的每个节点只需要加上pre，然后更新pre的值为pre加上当前节点的值即可

AC代码

/**
 * 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 pre=0;
    void traval(TreeNode* cur)
    {
        if(cur==nullptr)return;
        traval(cur->right);
        cur->val += pre;
        pre=cur->val;
        traval(cur->left);
    }
    TreeNode* convertBST(TreeNode* root) {
        traval(root);
        return root;
    }
};

108. 将有序数组转换为二叉搜索树

链接： 108. 将有序数组转换为二叉搜索树

解题思路

当我们面对解决问题时，首先要明确问题的具体要求。在这道题中，我们需要将一个有序数组转换为一棵二叉搜索树。这里的关键是理解二叉搜索树的特性：对于任意一个节点，它的左子树中的所有节点都小于它，而右子树中的所有节点都大于它。

接下来，我们可以使用递归来解决这个问题。递归是一种常用的解决复杂问题的方法，它将问题分解为更小的子问题来解决。

首先，我们需要确定递归的终止条件。在这道题中，当左边界大于右边界时，说明已经没有元素可用了，此时我们应该返回空节点。

接着，我们需要在递归的每一层中选择合适的节点值，并创建节点。我们可以选择数组中间的元素作为当前节点的值，然后创建一个新的节点。

接下来，我们需要递归地构建当前节点的左子树和右子树。左子树的范围是从左边界到中间元素的前一个位置，右子树的范围是从中间元素的后一个位置到右边界。

最后，我们返回当前节点，完成一次递归。

通过这样的递归过程，我们可以逐步构建出一棵符合要求的二叉搜索树。

在编写代码时，我们还需要注意一些细节。当计算中间位置时，为了避免整数溢出的问题，我们可以使用 int mid = left + ((right - left) / 2); 的方式来计算中间位置。

另外，在调用 traversal 函数时，我们传入的左边界 left 是 0，右边界 right 是 nums.size() - 1，因为题目中给出的数组是有序的且没有重复元素，所以这样的范围划分是合理的。

AC代码

/**
 * 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:
    TreeNode* traval(vector<int>& nums,int left,int right){
        if(left>right)return nullptr;
        int mid=left+(right-left)/2;
        TreeNode* node=new TreeNode(nums[mid]);
        node->left=traval(nums,left,mid-1);
        node->right=traval(nums,mid+1,right);
        return node;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return traval(nums,0,nums.size()-1);
    }
};


文章标签：
算法
关键词：
算法训练
算法二叉树
算法训练二叉树
幼稚十一
目录
相关文章
RossyYan
|
2天前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法（头歌教学实验平台习题） 【合集】
本任务旨在实现二叉树的遍历，包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义，并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑，以及层次遍历中队列的应用。最后提供了测试用例和预期输出，确保代码正确性。通过这些内容，帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
RossyYan
16 2
小山那边
|
16天前
|
存储 算法 Python
文件管理系统中基于 Python 语言的二叉树查找算法探秘
在数字化时代，文件管理系统至关重要。本文探讨了二叉树查找算法在文件管理中的应用，并通过Python代码展示了其实现过程。二叉树是一种非线性数据结构，每个节点最多有两个子节点。通过文件名的字典序构建和查找二叉树，能高效地管理和检索文件。相较于顺序查找，二叉树查找每次比较可排除一半子树，极大提升了查找效率，尤其适用于海量文件管理。Python代码示例包括定义节点类、插入和查找函数，展示了如何快速定位目标文件。二叉树查找算法为文件管理系统的优化提供了有效途径。
小山那边
47 5
光明顶阳顶天
|
2月前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码，实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
光明顶阳顶天
66 8
dufadayang
|
2月前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率？
选择合适的遍历算法，如按层次遍历树时使用广度优先搜索（BFS），中序遍历二叉搜索树以获得有序序列。优化数据结构，如使用线索二叉树减少空指针判断，自定义节点类增加辅助信息。利用递归与非递归的特点，避免栈溢出问题。多线程并行遍历提高速度，注意线程安全。缓存中间结果，避免重复计算。预先计算并存储信息，提高遍历效率。综合运用这些方法，提高二叉树遍历算法的效率。
dufadayang
71 5
zzy的aly
|
3月前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三)：Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合，涵盖了从基础到提高的多个算法题目及其解答。
zzy的aly
136 3
蓝桥杯练习题(三)：Python组之算法训练提高综合五十题
mao29955
|
2月前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些？
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法，在许多领域都有着不可或缺的应用，它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展，二叉树遍历算法也在不断地被优化和扩展，以适应新的应用场景和需求。
mao29955
61 0
aliyun4381607004
|
2月前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景，随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码，发现使用的`nativeBooster.saveModel`方法不支持OSS路径，而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令，帮助用户顺利迁移模型存储路径。
aliyun4381607004
96 1
java冯坚持
|
3月前
|
存储 算法 关系型数据库
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
这篇文章主要介绍了多路查找树的基本概念，包括二叉树的局限性、多叉树的优化、B树及其变体（如2-3树、B+树、B*树）的特点和应用，旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
java冯坚持
36 0
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
java冯坚持
|
3月前
|
存储 算法 搜索推荐
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
java冯坚持
44 0
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
努力学习的小廉
|
3月前
|
存储 算法
【二叉树】—— 算法题
【二叉树】—— 算法题
努力学习的小廉
25 0
【二叉树】—— 算法题

热门文章

最新文章

  • 1
    Python-OpenCV学习（十）用GrabCUt算法进行图片前景的提取
  • 2
    国密算法及简单使用
  • 3
    [PAL规范]SAP HANA PAL 数据处理装箱算法Binning编程规范BINNING
  • 4
    机器学习常见算法分类汇总
  • 5
    浪客剑心：位图法Bitmap算法分析
  • 6
    编码算法－Base64
  • 7
    WPF 心形线算法
  • 8
    《算法技术手册》一第3章 算法基础
  • 9
    【20160924】GOCVHelper MFC增强算法（5）
  • 10
    实现 MyBatis-Plus 中的配置加密功能（使用 AES 算法）
  • 1
    【Paddle】PCA线性代数基础 + 领域应用：人脸识别算法（1.1w字超详细：附公式、代码）
    131
  • 2
    BASE64的算法说明
    72
  • 3
    算法人生（1）：从“强化学习”看如何“战胜拖延”
    123
  • 4
    理解并应用机器学习算法：决策树
    153
  • 5
    【机器学习】在使用K-means聚类算法时，如何选择K的值？
    457
  • 6
    【机器学习】为什么K-means算法使用欧式距离度量？
    446
  • 7
    【机器学习】描述K-means算法的步骤
    163
  • 8
    【机器学习】K-means和KNN算法有什么区别？
    705
  • 9
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-2
    64
  • 10
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-1
    68

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    DataWorks智能交互式数据开发与分析之旅