669. Trim a Binary Search Tree -----(Medium)

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node's descendant should remain a descendant). It can be proven that there is a unique answer.

Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

 

Example 1:

Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]

Example 2:

Input: root = [3,0,4,null,2,null,null,1], low = 1, high = 3
Output: [3,2,null,1]

 

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• 0 <= Node.val <= 104
• The value of each node in the tree is unique.
• root is guaranteed to be a valid binary search tree.
• 0 <= low <= high <= 104

A:

递归啊，没别的方法

/**
 * 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) {
        return helper(root, low, high);
    }
private:
    TreeNode* helper(TreeNode* root, int low, int high ){
        if(!root)
            return root;
        if(root->val < low){
            return helper(root->right, low, high);
        }else if(root->val > high){
            return helper(root->left, low, high);
        }else{ // root->val is in range,  we then need delete both child-tree
            root->left = helper(root->left, low, high);
            root->right = helper(root->right, low, high);
            return root;
        }
    }
};

上面的代码，很快就过了。但是有 memory leak。  真正的工作代码中，应该加上delete（）
/**
 * 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) {
        return helper(root, low, high);
    }
private:
    TreeNode* helper(TreeNode* root, int low, int high ){
        if(!root)
            return root;
        if(root->val < low){
            auto res = helper(root->right, low, high);
            deleteTree(root->left);
            delete(root);
            return res;
        }else if(root->val > high){
            auto res = helper(root->left, low, high);
            deleteTree(root->right);
            delete(root);
            return res;
        }else{ // root->val is in range,  we then need delete both child-tree
            root->left = helper(root->left, low, high);
            root->right = helper(root->right, low, high);
            return root;
        }
    }
    
    void deleteTree(TreeNode* root){
        if(!root)
            return;
        deleteTree(root->left);
        deleteTree(root->right);
        delete(root);
    }
};

但是上面的代码，在LC中，有error，显示： 判题器可能还在用root指针。 
从error message 来看，leetcode会帮忙删除这些内存。
因此面试的时候，可以说。但是不需要写了