【代码随想录day 20】 力扣 669. 修剪二叉搜索树
视频讲解：https://www.bilibili.com/video/BV17P41177ud/?share_source=copy_web&vd_source=a935eaede74a204ec74fd041b917810c
文档讲解：https://programmercarl.com/0669.%E4%BF%AE%E5%89%AA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html#%E6%80%9D%E8%B7%AF
力扣题目：https://leetcode.cn/problems/trim-a-binary-search-tree/
主要思路：
- 遍历二叉树判断节点
- 如果节点的值小于区间，则左子树会更小，因此左子树全部删除，但不能直接连接右子树节点，因为右子树可能存在范围之外的节点，因此需要进入右子树继续遍历
- 如果节点值大于区间，右子树会更大，因此进入左子树遍历
- 单次递归返回情况，如果空节点则想上一层返回空节点。如果节点小于返回右节点。如果大于返回左节点。最后返回root根节点
class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {//判断终止条件if(root == NULL) return NULL;//如果节点值小于区间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;}
};