首页 > 编程语言 >代码随想录算法训练营第23天|669. 修剪二叉搜索树|108.将有序数组转换为二叉搜索树|538.把二叉搜索树转换为累加树|总结篇

代码随想录算法训练营第23天|669. 修剪二叉搜索树|108.将有序数组转换为二叉搜索树|538.把二叉搜索树转换为累加树|总结篇

时间:2024-03-18 17:03:14浏览次数:24  
标签:right TreeNode val int 随想录 二叉 搜索 root left

代码随想录算法训练营第23天|669. 修剪二叉搜索树|108.将有序数组转换为二叉搜索树|538.把二叉搜索树转换为累加树|总结篇

669. 修剪二叉搜索树

这道题目比较难,比 添加增加和删除节点难的多,建议先看视频理解。

题目链接/文章讲解:
https://programmercarl.com/0669.%E4%BF%AE%E5%89%AA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html 视频讲解: https://www.bilibili.com/video/BV17P41177ud

/**
 * 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 nullptr;
        if(root->val<low)
        {
            TreeNode* right=trimBST(root->right,low,high);// 寻找符合区间[low, high]的节点
            return right;
        }
        if(root->val>high)
        {
            TreeNode* left=trimBST(root->left,low,high);// 寻找符合区间[low, high]的节点
            return left;
        }
        root->left=trimBST(root->left,low,high);// root->left接入符合条件的左孩子
        root->right=trimBST(root->right,low,high);// root->right接入符合条件的右孩子
        return root;
    }
};

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

本题就简单一些,可以尝试先自己做做。

https://programmercarl.com/0108.%E5%B0%86%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
视频讲解:https://www.bilibili.com/video/BV1uR4y1X7qL

/**
 * 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* traversal(vector<int>& nums,int left,int right)//构造二叉搜索树,前序遍历
    {
        //确定递归终止条件
        //这里定义的是左闭右闭的区间,所以当区间 left > right的时候,就是空节点了。
        if(left>right)return NULL;

        int mid=(left+right)/2;
        TreeNode *root=new TreeNode(nums[mid]);
        //接着划分区间,root的左孩子接住下一层左区间的构造节点,右孩子接住下一层右区间构造的节点。
        root->left=traversal(nums,left,mid-1);
        root->right=traversal(nums,mid+1,right);

        return root;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int left,right;
        left=0;
        right=nums.size()-1;
        TreeNode* result=traversal(nums,left,right);
        return result;

    }
};

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

本题也不难,在 求二叉搜索树的最小绝对差 和 众数 那两道题目 都讲过了 双指针法,思路是一样的。

https://programmercarl.com/0538.%E6%8A%8A%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E8%BD%AC%E6%8D%A2%E4%B8%BA%E7%B4%AF%E5%8A%A0%E6%A0%91.html
视频讲解:https://www.bilibili.com/video/BV1d44y1f7wP

/**
 * 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 traversal(TreeNode* node)// 记录前一个节点的数值
    {
        if(node==NULL)return;
        traversal(node->right);//右
        node->val+=pre;//中
        pre=node->val;
        traversal(node->left);//左

    }
    TreeNode* convertBST(TreeNode* root) {
        traversal(root);
        return root;
    }
};

总结篇

https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E6%80%BB%E7%BB%93%E7%AF%87.html

标签:right,TreeNode,val,int,随想录,二叉,搜索,root,left
From: https://blog.csdn.net/2401_83080774/article/details/136711461

相关文章

  • 代码随想录算法训练营第27天|39. 组合总和|40.组合总和II|131.分割回文串
    代码随想录算法训练营第27天|39.组合总和|40.组合总和II|131.分割回文串详细布置39.组合总和本题是集合里元素可以用无数次,那么和组合问题的差别其实仅在于startIndex上的控制题目链接/文章讲解:https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%9......
  • 代码随想录算法训练营第五十天 | 123. 买卖股票的最佳时机 III,188. 买卖股票的最佳时
    123.买卖股票的最佳时机III 已解答困难 相关标签相关企业 给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。注意:你不能同时参与多笔交易(你必须在再次购......
  • 洛谷题单指南-二叉树-P3884 [JLOI2009] 二叉树问题
    原题链接:https://www.luogu.com.cn/problem/P3884题意解读:要计算二叉树的深度、宽度、节点间的距离,深度、宽度的概念很好理解,节点间的距离描述是:节点u,v之间的距离表示从u到v的最短有向路径上向根节点的边数的两倍加上向叶节点的边数。说人话就是:u到v的距离=uv最近公共祖先到u......
  • 自定义edge地址搜索栏
    在bing上搜索计算机相关内容,前两页csdn能占十之七八九,内容能参考的十之一二,毕竟还能看,这回csdn呱噪地把顶部广告栏直接加到页面的三有其一,翻看内容很不适,意思就是不登录就别看了,没辙,还是得屏蔽。因之前就屏蔽过一次,重装系统后没加上,这回照着旧路子再走一遍,edge点设置->隐私,搜索和......
  • 代码随想录算法训练营第四十八天 | 122.买卖股票的最佳时机II ,121. 买卖股票的最佳时
    122.买卖股票的最佳时机II 已解答中等 相关标签相关企业 给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,......
  • 代码随想录算法训练营第十三天| 239. 滑动窗口最大值 347. 前 K 个高频元素
    239.滑动窗口最大值https://leetcode.cn/problems/sliding-window-maximum/description/publicint[]maxSlidingWindow(int[]nums,intk){int[]res=newint[nums.length-k+1];intindex=0;ArrayDeque<Integer>deque=newArray......
  • Linux vscode右上角布局按钮显示 & 顶部不显示搜索栏
    以下设置均在ubuntu上测试,windows可能类似。开启或关闭右上角布局按钮:勾选layoutcontrol同时注意,window.titleBarStyle需要设置为custom才会生效。关闭顶部中间的搜索框中间有个很占地方的搜索框设置里搜索commandcenter,取消勾选即可。(同样,titlebarstyle需要设置为cust......
  • Github高级搜索【指定日期区间,星星数,用户仓库名多条件精确搜索】
    小伙伴们号,欢迎关注,一起学习,无限进步GitHub高级搜索允许用户使用多种条件来精确查找所需的仓库、文件和代码。以下是对GitHub高级搜索的最全、详细总结说明:文章目录关键字搜索仓库名搜索用户搜索组织搜索文件搜索语言搜索星星数搜索更新时间搜索授权搜索组合搜索排......
  • 代码随想录算法训练营第十天|LeetCode 20.有效的括号、1047.删除字符串中的所有相邻重
    20.有效的括号题目链接:https://leetcode.cn/problems/valid-parentheses/description/解题思路:题目转化:三种类型的括号,需要做匹配匹配规则是:左右括号的类型要匹配、数量要一致,而且要按照顺序匹配例子是:“()”、“(){}[]”、“(([]))”条件转化:按照顺序匹配:......
  • 二叉树的广度优先遍历(力扣102)
    文章目录题目前知BFS是什么?队列的基本操作有什么?题解一、思路二、解题方法三、Code总结题目Problem:102.二叉树的层序遍历给你二叉树的根节点root,返回其节点值的层序遍历。(即逐层地,从左到右访问所有节点)。前知BFS是什么?树的广度优先遍历(BFS)是一种遍......