C++算法练习-day48——669.修剪二叉搜索树

题目来源：. - 力扣（LeetCode）

题目思路分析

题目要求实现一个函数 trimBST，该函数用于修剪一棵二叉搜索树（BST），使得修剪后的树中所有节点的值都在给定的范围 [low, high] 内。修剪后的树应该仍然是一棵二叉搜索树，并且尽可能小（即，只包含给定范围内的节点）。

思路分析：

1. 递归处理：由于二叉搜索树的性质（左子树所有节点值小于根节点值，右子树所有节点值大于根节点值），我们可以使用递归的方法来处理这个问题。
2. 边界条件：
   • 如果当前节点为空（即，已经遍历到叶子节点的下一层），直接返回 nullptr。
   • 如果当前节点的值小于 low，说明当前节点及其左子树的所有节点值都小于 low，因此应该被修剪掉。此时，递归地修剪右子树，并返回修剪后的右子树作为新的根节点。
   • 如果当前节点的值大于 high，同理，应该修剪掉当前节点及其右子树，递归地修剪左子树，并返回修剪后的左子树作为新的根节点。
3. 修剪子树：如果当前节点的值在给定范围内，则递归地修剪其左子树和右子树，并更新当前节点的左右子指针。

代码:

/**  
 * 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) {  
        // 如果当前节点为空，直接返回 nullptr  
        if(!root){  
            return nullptr;  
        }  
        // 如果当前节点的值小于 low，修剪掉当前节点及其左子树，递归修剪右子树  
        if(root->val < low){  
            return trimBST(root->right, low, high);  
        }  
        // 如果当前节点的值大于 high，修剪掉当前节点及其右子树，递归修剪左子树  
        else if(root->val > high){  
            return trimBST(root->left, low, high);  
        }  
        // 当前节点的值在给定范围内，递归修剪左右子树  
        else{  
            root->left = trimBST(root->left, low, high);  
            root->right = trimBST(root->right, low, high);  
        }  
        // 返回修剪后的树  
        return root;  
    }  
};

知识点摘要

1. 二叉搜索树（BST）：一种特殊的二叉树，其中每个节点的值都大于其左子树所有节点的值，且小于其右子树所有节点的值。
2. 递归：一种在函数内部调用自身的编程技巧，常用于解决可以分解为相似子问题的问题。
3. 边界条件处理：在递归函数中，正确处理边界条件（如空节点）是避免无限递归和错误结果的关键。

通过递归地修剪二叉搜索树，我们可以高效地解决给定范围内的节点修剪问题。递归方法利用了二叉搜索树的性质，使得问题可以分解为更小的子问题，从而简化了解决方案。在处理递归问题时，注意边界条件的处理是非常重要的，它确保了函数的正确性和稳定性。通过这种方法，我们不仅修剪了树，还保持了修剪后树作为二叉搜索树的性质。