代码随想录算法训练营第二十天| 669. 修剪二叉搜索树 108.将有序数组转换为二叉搜索树 538.把二叉搜索树转换为累加树

669. 修剪二叉搜索树

思路

递归法： 

需要思考清楚，如果当前节点<low，那么就返回递归它的右节点，而不是自己取判断，找出来一个合适的节点，这样的话会越想越乱

代码：

 1 TreeNode* trimBST_cursor(TreeNode* root, int low, int high) {
 2     if (!root) return nullptr;
 3 
 4     if (root->val < low)
 5     {
 6         return trimBST_cursor(root->right, low, high);
 7     }
 8 
 9     if (root->val > high)
10     {
11         return trimBST_cursor(root->left, low, high);
12     }
13 
14     if (root->left)
15     {
16         root->left = trimBST_cursor(root->left, low, high);
17     }
18 
19     if (root->right)
20     {
21         root->right = trimBST_cursor(root->right, low, high);
22     }
23 
24     return root;
25 }

迭代法：

需要先把当前的root，放到符合标准的区间里，这样不管左子树的右孩子，再怎么大，也不会大过root，所以他也就不会超过high

代码

 1 TreeNode* trimBST(TreeNode* root, int low, int high) {
 2     if (!root) return nullptr;
 3 
 4     //当前root位于最近的[]范围里
 5     while (root&&(root->val<low||root->val>high))
 6     {
 7         if (root->val < low)
 8             root = root->right;
 9         else if (root->val > high)
10             root = root->left;
11     }
12 
13     //让cur = root，开始向左遍历，如果左孩子小于low，那么就一直遍历它的右孩子，直到它的右孩子>low
14     auto curNode = root;
15     while (curNode)
16     {
17         while (curNode->left && curNode->left->val < low)
18         {
19             curNode->left = curNode->left->right;
20         }
21         //遇到一个左孩子小于的话，那么就把他删掉
22         curNode = curNode->left;
23     }
24 
25     curNode = root;
26     while (curNode)
27     {
28         while (curNode->right && curNode->right->val > high)
29         {
30             curNode->right = curNode->right->left;
31         }
32 
33         curNode = curNode->right;
34     }
35 
36     return root;
37 }