首页 > 编程语言 >代码随想录算法 - 二叉树7

代码随想录算法 - 二叉树7

时间:2024-09-17 09:23:39浏览次数:10  
标签:right 随想录 节点 算法 二叉树 null root curNode left

题目1 669. 修剪二叉搜索树

给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在 唯一的答案

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意,根节点可能会根据给定的边界发生改变。

示例 1:

img

输入:root = [1,0,2], low = 1, high = 2
输出:[1,null,2]

示例 2:

img

输入:root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出:[3,2,null,1]

提示:

  • 树中节点数在范围 [1, 104]
  • 0 <= Node.val <= 104
  • 树中每个节点的值都是 唯一
  • 题目数据保证输入是一棵有效的二叉搜索树
  • 0 <= low <= high <= 104

思路

既然搜索后要继续保持树为二叉搜索树,则应该移除范围外的节点,并保留范围内的节点。因此,当节点的val不在范围内时,需要返回相应的左节点或者右节点。

代码

//递归法 
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(root == nullptr)
        {
            return root;
        }
        if(root->val < low)
        {
            return trimBST(root->right, low, high);
        }
        else if(root->val > high)
        {
            return trimBST(root->left, low, high);
        }
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        return root;
    }
};

代码

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        while(root)
        {
            if(root->val < low)
                root = root->right;
            else if(root->val > high)
                root = root->left;
            else
                break;
        }
        TreeNode* curNode = root;
        while(curNode)
        {
            if(curNode->left && curNode->left->val < low)
            {
                curNode->left = curNode->left->right;
            }
            else
                curNode = curNode->left;
        }
        curNode = root;
        while(curNode)
        {
            if(curNode->right && curNode->right->val > high)
            {
                curNode->right = curNode->right->left;
            }
            else
                curNode = curNode->right;
        }
        return root;
    }
};

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

给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵

平衡

二叉搜索树。

示例 1:

img

输入:nums = [-10,-3,0,5,9]
输出:[0,-3,9,-10,null,5]
解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:

示例 2:

img

输入:nums = [1,3]
输出:[3,1]
解释:[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums严格递增 顺序排列

思路

使用递归和分而治之的思想,每次处理数组中中间的节点,并让中间节点指向新的子节点;使用递归也是类似的思路,每次处理一个范围的中间节点,范围用额外的2个queue来保存。

代码

class Solution {
public:
    TreeNode* createTree(vector<int>& nums, int lft, int rht)
    {
        if(lft > rht)
            return nullptr;
        TreeNode* curNode = new TreeNode(nums[(rht + lft) / 2]);
        curNode->left = createTree(nums, lft, (rht + lft) / 2 - 1);
        curNode->right = createTree(nums, (lft + rht) / 2 + 1, rht);
        return curNode;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return createTree(nums, 0, nums.size() - 1);
    }
};

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

给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下,二叉搜索树满足下列约束条件:

  • 节点的左子树仅包含键 小于 节点键的节点。
  • 节点的右子树仅包含键 大于 节点键的节点。
  • 左右子树也必须是二叉搜索树。

注意:本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 1:

img

输入:[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出:[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2:

输入:root = [0,null,1]
输出:[1,null,1]

示例 3:

输入:root = [1,0,2]
输出:[3,3,2]

示例 4:

输入:root = [3,2,4,1]
输出:[7,9,4,10]

提示:

  • 树中的节点数介于 0104 之间。
  • 每个节点的值介于 -104104 之间。
  • 树中的所有值 互不相同
  • 给定的树为二叉搜索树。

思路

因为二叉搜索树的最右侧节点是最大的,因此使用翻转过的中序遍历,按照右当前节点左的顺序遍历并累加节点值就能保证生产的结果为累加树。

递归法

class Solution {
public:
    int curNum = 0;
    TreeNode* convertBST(TreeNode* root) {
        if(root == nullptr)
            return root;
        root->right = convertBST(root->right);
        root->val += curNum;
        curNum = root->val;
        root->left = convertBST(root->left);
        return root;
    }
};

迭代法

class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        if(root == nullptr)
            return root;
        stack<TreeNode*> nodeStack;
        nodeStack.push(root);
        int num = 0;
        while(!nodeStack.empty())
        {
            TreeNode* curNode = nodeStack.top();
            if(curNode != nullptr)
            {
                nodeStack.push(nullptr);
                if(curNode->right)
                {
                    nodeStack.push(curNode->right);
                }
            }
            else
            {
                nodeStack.pop();
                curNode = nodeStack.top();
                nodeStack.pop();
                curNode->val += num;
                num = curNode->val;
                if(curNode->left)
                {
                    nodeStack.push(curNode->left);
                }
            }
        }
        return root;
    }
};

标签:right,随想录,节点,算法,二叉树,null,root,curNode,left
From: https://www.cnblogs.com/code4log/p/18416911

相关文章

  • Java算法总结
    文章目录一、链表相关1.1从尾到头打印单链表[要求方式1:反向遍历。方式2:Stack栈]1.2josephu问题(使用带尾指针的循环链表)二、动态规划2.1斐波那契数列2022.4.182.2青蛙上台阶2022.4.18三、位运算符3.1二进制中1的个数2022.4.18四、回溯算法4.1打印从1到最大的......
  • 九、并查集-算法总结
    文章目录九、并查集9.1简介9.2数据结构9.2.1初始化9.2.2Quick-Find9.2.3Quick-Union9.2.4WeightedQuickUnion九、并查集9.1简介并查集用于处理不相交集合的合并与查询问题,常见操作有:查询:查询元素属于哪个集合,可用于判断元素是否在一个集合中合并:合并两......
  • 常见的限流算法
    限流算法是用于控制访问频率、保护系统免受过载攻击的重要手段。常见的限流算法有以下几种,每种算法都有不同的应用场景和优缺点。下面是几种常见的限流算法的详细介绍:1.计数器算法(Counter)原理计数器算法是最简单的限流算法。它在固定的时间窗口内记录请求的次数,一旦请求次......
  • 【智能算法应用】粒子群算法求解最小生成树问题
    目录1.最小生成树MST2.算法原理3.算法过程4.结果展示5.参考文献6.代码获取1.最小生成树MST最小生成树(MinimumSpanningTree,MST)是在给定的加权无向图中寻找一个边的子集,使得这些边构成的树包含图中的所有顶点,并且边的总权重尽可能小。如果图......
  • 【智能算法应用】海洋捕食者算法求解TSP问题
    目录1.算法原理2.TSP数学模型3.结果展示4.参考文献5.代码获取1.算法原理【智能算法】海洋捕食者算法(MPA)原理及实现2.TSP数学模型旅行商问题(TSP)是一种著名的组合优化问题,它涉及寻找给定一组城市及其之间的距离或成本,如何规划一条最短的路径,使得旅行商从起点出发,......
  • 【智能算法应用】飞蛾扑火算法求解TSP问题
    目录1.算法原理2.TSP数学模型3.结果展示4.参考文献5.代码获取1.算法原理【智能算法】飞蛾扑火算法(MFO)原理及实现2.TSP数学模型旅行商问题(TSP)是一种著名的组合优化问题,它涉及寻找给定一组城市及其之间的距离或成本,如何规划一条最短的路径,使得旅行商从起点出发,访......
  • 文心一言 VS 讯飞星火 VS chatgpt (348)-- 算法导论23.2 7题
    七、假定图G的一棵最小生成树已经被计算出来。如果在图中加入一个新结点及其相关的新边,我们需要多少时间来对最小生成树进行更新?如果要写代码,请用go语言。文心一言:在图中加入一个新节点及其相关边后,要更新最小生成树(MST),通常意味着需要重新计算包含新节点的最小生成树,因为新节点的加......
  • Day17 二叉树part07| LeetCode 235. 二叉搜索树的最近公共祖先 ,701.二叉搜索树中的插
    235.二叉搜索树的最近公共祖先235.二叉搜索树的最近公共祖先利用二叉搜索树的特性——有序树,可知,如果中间节点是p和q的公共节点,那个中间节点的数值一定在[p,q]区间因此,从根节点往下搜索,遇到的第一个位于[p,q]或[q,p]区间的节点就是最近公共祖先classSolution{......
  • leetcode刷题day20|二叉树Part08(669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索
    669.修剪二叉搜索树思路:理解了删除二叉搜索树中的节点,这个题理解起来就不难了。还是选用中序遍历递归。递归三步曲:1、传入参数:根节点,最小值,最大值;返回值为根节点;2、终止条件:如果节点为空,直接返回空;3、递归逻辑:如果最小值小于该节点,递归调用该节点的右孩子(检查右孩子......
  • leetcode刷题day19|二叉树Part07(235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的
    235.二叉搜索树的最近公共祖先思路:二叉搜索树首先考虑中序遍历。根据二叉搜索树的特性,如果p,q分别在中间节点的左右两边,该中间节点一定是最近公共祖先,如果在同一侧,则递归这一侧即可。递归三部曲:1、传入参数:根节点,p,q,返回节点。2、终止条件:因为p,q一定存在,所以不会遍历到......