目录
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, 104]内 0 <= Node.val <= 104- 树中每个节点的值都是 唯一 的
- 题目数据保证输入是一棵有效的二叉搜索树
0 <= low <= high <= 104
题解
首先试试递归。第一步考虑递归出口，对于当前正在处理的节点：
-
若为空节点，直接返回
-
若节点值小于
low，返回其右节点此时，当前节点的左子树中的值，全都小于当前节点值，自然也全都小于
low，故可以直接修剪掉左子树，用右子树取代当前（根）节点。下面情况同理。 -
若节点值大于
high，返回其左节点
否则，当前节点处于目标区间内，递归处理其左右子树即可。整体代码如下：
TreeNode *trimBST(TreeNode *root, int low, int high)
{
// 空节点直接返回
if (!root)
return nullptr;
// 节点值不在目标区间
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;
}
接下来再试试迭代法，需要注意的是 ⚠️
- 一开始就要让
root指针先走到目标区间内 - 迭代时注意，修剪掉某棵子树后，新接过来的子树可能还是不满足条件，故此处的逻辑判断不能只用一个
if，而要用while
整体代码如下：
TreeNode *trimBST(TreeNode *root, int low, int high)
{
// 先让root指针走到目标区间内的值
while (root && (root->val < low || root->val > high)) {
if (root->val < low)
root = root->right;
if (root->val > high)
root = root->left;
}
// 此时的root已经处于目标区间内了，处理其左子树
TreeNode *cur = root;
while (cur) {
while (cur->left && cur->left->val < low) // 注意此处要用while判断
cur->left = cur->left->right;
cur = cur->left;
}
// 此时的root已经处于目标区间内了，处理其右子树
cur = root;
while (cur) {
while (cur->right && cur->right->val > high) // 注意此处要用while判断
cur->right = cur->right->left;
cur = cur->right;
}
return root;
}
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 <= 104-104 <= nums[i] <= 104nums按 严格递增 顺序排列
题解
题目要求生成的BST是 平衡 的，即要尽量让各节点的左右子树高度相同，故联想到 二分 的思想：
- 每次取当前数组的中位数作为根节点
- 其左边部分的子数组递归生成其左子树
- 其右边部分的子数组递归生成其右子树
可以任意写一个简单的递增序列，模拟一下，就理解了。
代码（C++）
TreeNode *getRoot(const auto &nums, int left, int right) {
// 递归出口：左右指针错开
if (left > right)
return nullptr;
// 当前数组切片的中位数作为根节点
int mid = left + (right - left) / 2;
TreeNode *root = new TreeNode(nums[mid]);
root->left = getRoot(nums, left, mid - 1);
root->right = getRoot(nums, mid + 1, right);
return root;
}
TreeNode *sortedArrayToBST(vector<int> &nums)
{
return getRoot(nums, 0, nums.size() - 1);
}
也可以考虑迭代法，但是需要用多个数据结构存储子数组的左右指针和树节点等，代码复杂不少，这里参考 代码随想录 上Carl的解法：
TreeNode* sortedArrayToBST(vector<int>& nums) {
if (nums.size() == 0) return nullptr;
TreeNode* root = new TreeNode(0); // 初始根节点
queue<TreeNode*> nodeQue; // 放遍历的节点
queue<int> leftQue; // 保存左区间下标
queue<int> rightQue; // 保存右区间下标
nodeQue.push(root); // 根节点入队列
leftQue.push(0); // 0为左区间下标初始位置
rightQue.push(nums.size() - 1); // nums.size() - 1为右区间下标初始位置
while (!nodeQue.empty()) {
TreeNode* curNode = nodeQue.front();
nodeQue.pop();
int left = leftQue.front(); leftQue.pop();
int right = rightQue.front(); rightQue.pop();
int mid = left + ((right - left) / 2);
curNode->val = nums[mid]; // 将mid对应的元素给中间节点
if (left <= mid - 1) { // 处理左区间
curNode->left = new TreeNode(0);
nodeQue.push(curNode->left);
leftQue.push(left);
rightQue.push(mid - 1);
}
if (right >= mid + 1) { // 处理右区间
curNode->right = new TreeNode(0);
nodeQue.push(curNode->right);
leftQue.push(mid + 1);
rightQue.push(right);
}
}
return root;
}
538. 把二叉搜索树转换为累加树
题目描述
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
注意： 本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同
示例 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]
示例 3：
输入：root = [1,0,2]
输出：[3,3,2]
示例 4：
输入：root = [3,2,4,1]
输出：[7,9,4,10]
提示：
- 树中的节点数介于
0和104之间。 - 每个节点的值介于
-104和104之间。 - 树中的所有值 互不相同 。
- 给定的树为二叉搜索树。
题解
首先明确一下累加思路：
由于大于等于最大节点的累计值，就是该节点的值本身，所以应该从最大的数开始累加，同时维护一个累计值——每次将累计值加上当前节点值。
比如之后，大于等于第二大节点值的累计值，就是第一次的累计值，加上第二大节点的值。以此类推，就能得到所有节点的新值。
可以结合题目描述中示例1的图进行模拟，便于理解
那么我们自然需要按照节点值的大小，从大到小处理。可以考虑用一个优先队列，按照节点值从大到小存储各节点，然后依次取出队头元素处理：
TreeNode *convertBST(TreeNode *root)
{
if (!root)
return nullptr;
// 用一个优先队列，按原节点值从大到小存储所有节点
auto cmp = [](TreeNode *a, TreeNode *b) {
return a->val < b->val;
};
priority_queue<TreeNode *, vector<TreeNode *>, decltype(cmp)> pq(cmp);
// 层序遍历
queue<TreeNode *> q;
q.push(root);
while (!q.empty())
{
int size = q.size();
for (int i = 0; i < size; i++)
{
TreeNode *cur = q.front();
q.pop();
pq.push(cur); // 将节点加入优先队列
if (cur->left)
q.push(cur->left);
if (cur->right)
q.push(cur->right);
}
}
// 按原节点值从大到小更新节点值
int biggerSum = 0; // 大于等于当前节点值的所有节点值之和
while (!pq.empty())
{
biggerSum += pq.top()->val;
pq.top()->val = biggerSum;
pq.pop();
}
return root;
}
不过上述算法实际上可以应用于任意二叉树，也就是说它并没有利用二叉搜索树的性质特点。我们知道，二叉搜索树的中序遍历结果是一个递增序列，那么将它反过来，不就是我们需要的节点值递减序列了吗？
所以，我们可以采取逆中序遍历，在遍历的过程中完成累计和更新操作。代码和中序遍历差不多，调整一下顺序即可。若采用递归：
int biggerSum = 0;
TreeNode *convertBST(TreeNode *root)
{
// 逆中序遍历——右中左
if (!root)
return nullptr;
root->right = convertBST(root->right); // 右
biggerSum += root->val; // 更新节点值之和
root->val = biggerSum; // 中
root->left = convertBST(root->left); // 左
return root;
}
若采用迭代：
TreeNode *convertBST(TreeNode *root)
{
// 基于统一迭代法
if (!root)
return nullptr;
int biggerSum = 0;
stack<TreeNode *> st;
st.push(root);
while (!st.empty())
{
TreeNode *cur = st.top();
st.pop();
if (cur)
{
// 要得到“右中左”的逆中序遍历结果，则应按照“左中右”入栈
if (cur->left)
st.push(cur->left); // 左
st.push(cur); // 中
st.push(nullptr); // 空节点标记
if (cur->right)
st.push(cur->right); // 右
}
else
{
biggerSum += st.top()->val;
st.top()->val = biggerSum; // 更新节点值
st.pop();
}
}
return root;
}