LC.669 ｜ 修剪二叉搜索树 ｜ 树 ｜ 递归与重连

输入：
二叉搜索树的根节点root，以及最小边界low和最大边界high。

要求：
修剪该二叉搜索树，使得所有节点的值都在[low, high]之间。
注意：可能需要改变树的根节点，修剪后的树必须保持二叉搜索树的相对结构（即：父子关系虽变，但原来的后代如果保留下来了，相对大小关系不变）。

输出：
修剪好的二叉搜索树的新的根节点TreeNode*。

思路：

这是一道经典的递归题目，借着这题来回顾一下递归三要素。

1. 确定递归函数的定义：

• 函数trim(root, low, high)的含义是：“给我一棵树的根节点root，我帮你把不符合[low, high]范围的节点剪掉，然后把修剪后合法的树的根节点返回给你。”
• 这点非常重要：我们通过返回值来接收修剪后的结果，并用来更新父节点的指针。

2. 确定递归终止条件：

• 如果root为空（nullptr），说明遍历到了空节点，没什么好修剪的，直接返回nullptr。

3. 确定单层递归逻辑（核心剪枝逻辑）：
利用二叉搜索树（BST）的有序性（左 < 根 < 右）进行判断：

• 情况 A：当前节点太小了 (root->val < low)

  • 既然当前节点都比low小，那么根据 BST 性质，它的左子树里所有节点肯定都比low小。
  • 决策：当前节点和它的左子树都要被“抛弃”。
  • 希望：它的右子树里可能还有比当前节点大、且在[low, high]范围内的节点。
  • 操作：直接去修剪右子树，并把修剪后的结果作为新的根返回。即return trim(root->right, ...)。

• 情况 B：当前节点太大了 (root->val > high)

  • 同理，既然当前节点都比high大，那么它的右子树肯定全废了。
  • 决策：当前节点和它的右子树都要被“抛弃”。
  • 希望：它的左子树里可能还有比当前节点小、且符合要求的节点。
  • 操作：直接去修剪左子树，并把结果返回。即return trim(root->left, ...)。

• 情况 C：当前节点在范围内 (low <= root->val <= high)

  • 决策：当前节点是合法的，必须保留。
  • 隐患：虽然当前节点合法，但它的左孩子可能太小，右孩子可能太大。
  • 操作：
    1. 让左孩子去接受修剪：root->left = trim(root->left, ...)
    2. 让右孩子去接受修剪：root->right = trim(root->right, ...)
    3. 左右都修整好了，返回当前节点root。

复杂度：

• 时间复杂度：O(N)
  • 每个节点最多被访问一次。
• 空间复杂度：O(H)
  • H 为树的高度，递归调用栈的深度。

classSolution{public:TreeNode*trimBST(TreeNode*root,intlow,inthigh){returntrim(root,low,high);}TreeNode*trim(TreeNode*root,intlow,inthigh){if(!root){returnnullptr;}if(root->val>=low&&root->val<=high){root->left=trim(root->left,low,high);root->right=trim(root->right,low,high);returnroot;}elseif(root->val<low){returntrim(root->right,low,high);}elseif(root->val>high){returntrim(root->left,low,high);}returnroot;}};