0.引言

● 669. 修剪二叉搜索树
● 108.将有序数组转换为二叉搜索树
● 538.把二叉搜索树转换为累加树

669. 修剪二叉搜索树

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

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

示例 1：

image.png

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

示例 2：

image.png

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

提示：

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

Discussion | Solution

递归法

/*
 * @lc app=leetcode.cn id=669 lang=cpp
 *
 * [669] 修剪二叉搜索树
 */

// @lc code=start
/**
 * 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) {
    return dfs(root, low, high);
  }

 private:
  //  后序遍历
  TreeNode* dfs(TreeNode* node, int low, int high) {
    if (node == nullptr) {
      return nullptr;
    }
    if (node->val < low) {
      return dfs(node->right, low, high);
    }
    if (node->val > high) {
      return dfs(node->left, low, high);
    }
    node->left = dfs(node->left, low, high);
    node->right = dfs(node->right, low, high);
    return node;
  }
};
// @lc code=end

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

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

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

示例 1：

image.png

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

image.png

image.png

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

提示：

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

Discussion | Solution

递归法

/*
 * @lc app=leetcode.cn id=108 lang=cpp
 *
 * [108] 将有序数组转换为二叉搜索树
 */

// @lc code=start
/**
 * 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* sortedArrayToBST(vector<int>& nums) {
    return dfs(nums);
  }

 private:
  TreeNode* dfs(std::vector<int> nums) {
    if (nums.empty()) {
      return nullptr;
    }
    if (nums.size() == 1) return new TreeNode(nums[0]);
    int mid = nums.size() / 2;

    TreeNode* node = new TreeNode(nums[mid]);

    std::vector<int> left(nums.begin(), nums.begin() + mid);
    std::vector<int> right(nums.begin() + mid + 1, nums.end());

    node->left = dfs(left);
    node->right = dfs(right);
    return node;
  }
};
// @lc code=end

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

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

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

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

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

示例 1：

image.png

输入：[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 和 10<sup>4</sup>之间。
• 每个节点的值介于 -10<sup>4</sup> 和 10<sup>4</sup> 之间。
• 树中的所有值 互不相同 。
• 给定的树为二叉搜索树。

Discussion | Solution

递归法

之前还想复杂了：

/*
 * @lc app=leetcode.cn id=538 lang=cpp
 *
 * [538] 把二叉搜索树转换为累加树
 */

// @lc code=start
/**
 * 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* convertBST(TreeNode* root) {
    if (root == nullptr) return nullptr;
    int cumulate_val = 0;
    bool is_right_most = false;
    dfs(root, cumulate_val, is_right_most);
    return root;
  }

 private:
  // 右中左的遍历顺序
  void dfs(TreeNode* node, int& cumulate_val, bool& is_right_most) {
    // 找到最右边那个
    if (node->left == nullptr && node->right == nullptr && !is_right_most) {
       is_right_most = true;
       cumulate_val = node->val;
       return;
     }
    // 正常的终止条件
    // if (node->left == nullptr && node->right == nullptr) {
    //   node->val += cumulate_val;
    //   cumulate_val = node->val;
    //   return;
    // }
    if(node==nullptr) return;
    if (node->right) dfs(node->right, cumulate_val, is_right_most);
    node->val += cumulate_val;
    cumulate_val = node->val;
    if (node->left) dfs(node->left, cumulate_val, is_right_most);
  }
};
// @lc code=end

这种情况，[2,1]这种case过不了，其实完全不用人为的去找，由于遍历顺序决定，天然的就会去找到起始的位置：

/*
 * @lc app=leetcode.cn id=538 lang=cpp
 *
 * [538] 把二叉搜索树转换为累加树
 */

// @lc code=start
/**
 * 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* convertBST(TreeNode* root) {
    if (root == nullptr) return nullptr;
    int cumulate_val = 0;
    bool is_right_most = false;
    dfs(root, cumulate_val);
    return root;
  }

 private:
  // 右中左的遍历顺序
  void dfs(TreeNode* node, int& cumulate_val) {
    if(node==nullptr) return;
    dfs(node->right, cumulate_val);
    node->val += cumulate_val;
    cumulate_val = node->val;
    dfs(node->left, cumulate_val);
  }
};
// @lc code=end