leetcode 669. Trim a Binary Search Tree 修建二叉搜索树BST + 深度优先遍历DFS

矫情吗；* 2022-06-03 06:53 116阅读 0赞

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in \[L, R\] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

Example 1:  
Input:  
1  
/ \\  
0 2

L = 1  
R = 2

Output:  
1  
\\  
2  
Example 2:  
Input:  
3  
/ \\  
0 4  
\\  
2  
/  
1

L = 1  
R = 3

Output:  
3  
/  
2  
/  
1

这道题让我们修剪一棵二叉搜索树，给了个边界范围\[L, R\], 所有不在这个范围内的结点应该被移除掉，但是仍需要保留二叉搜索树的性质，即左<根<右，有时候是小于等于

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    /*
    struct TreeNode 
    {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    class Solution 
    {
    public:
        TreeNode* trimBST(TreeNode* root, int L, int R) 
        {
            if (root == NULL)
                return root;
            else if (root->val < L)
                return trimBST(root->right, L, R);
            else if (root->val > R)
                return trimBST(root->left, L, R);
            else
            {
                root->left = trimBST(root->left, L, R);
                root->right = trimBST(root->right, L, R);
                return root;
            }
        }
    };