LeetCode 669. 修剪二叉搜索树

题目链接：669. 修剪二叉搜索树
文章讲解：代码随想录#669. 修剪二叉搜索树
视频讲解：你修剪的方式不对，我来给你纠正一下！| LeetCode：669. 修剪二叉搜索树

题目描述

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

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

示例1

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

示例2

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

提示

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

思路

愣一看没啥思路，感觉就是要重构二叉树呢，直接上两张图思路立马就清晰了。

对于上图的二叉树，节点0和节点4不符合要求，需要将节点0的右孩子节点2指向节点3的左孩子，节点3的右孩子指向NULL。

递归参考代码

struct TreeNode* trimBST(struct TreeNode* root, int low, int high) {
    if (root == NULL) return root;
    if (root->val < low) { // 节点小于最小值，向右孩子遍历，找到符合区间的节点
        return trimBST(root->right, low, high);
    }
    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;
}

---

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

题目链接：108.将有序数组转换为二叉搜索树
文章讲解：代码随想录#108.将有序数组转换为二叉搜索树
视频讲解：构造平衡二叉搜索树！| LeetCode：108.将有序数组转换为二叉搜索树

题目描述

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例1

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9]

示例2

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

提示

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums 按 严格递增 顺序排列

思路

过年期间事情比较多，导致落下好多题，从昨天才开始赶进度，今天题目只完成一道，明天继续补

参考代码

待补充

---

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

题目链接：538.把二叉搜索树转换为累加树
文章讲解：代码随想录#538.把二叉搜索树转换为累加树
视频讲解：LeetCode：538.把二叉搜索树转换为累加树

题目描述

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

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

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

示例1

输入：[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]

提示

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

思路

参考代码

待补充