修剪二叉搜索树(力扣669)

这道题还是比较复杂，在递归上与之前写过的二叉树的题目都有所不同。如果当前递归到的子树的父节点不在范围中，我们根据节点数值的大小选择进行左递归还是右递归。为什么找到了不满足要求的节点之后，还要进行递归呢？因为该不满足要求的父节点的子树中可能存在满足要求的节点，我们要不断递归子树寻找这些满足要求的节点并向上返回，直到遇到空节点为止。注意这里递归函数的返回值为指向节点的指针，用来返回满足要求的节点。另外，递归到的子树的父节点满足要求时，需要进行链表的连接操作，刚好接住前面所说的满足要求的节点，最后再向上返回该节点，用于之后的连接。大家可以结合我下面的代码及注释理解此题。

代码及注释如下：

/*** 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) {//终止条件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;}//如果当前节点在范围中，则将当前节点与子树父节点连接TreeNode* a =  trimBST(root -> left,low,high);TreeNode* b = trimBST(root -> right,low,high);root -> left = a;root -> right = b;//返回连接后的新子树父节点return root;}
};