trim-a-binary-search-tree

Trim a Binary Search Tree – LeetCode 669

Problem

Description

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.

Answer

Original

Code

/**
 * Definition for a binary tree node.
 * 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){
            if(root->val < L)
                return trimBST(root->right, L, R);
            else if(R < root->val)
                return trimBST(root->left, L, R);
            else {
                root->left = trimBST(root->left, L, R);
                root->right = trimBST(root->right, L, R);
                return root;
            }
        } else
            return nullptr;
    }
};

思路

简单的DFS删除，注意维护返回的根节点。时间复杂度$O(n)$，空间复杂度$O(n)$。
耗时$8$ ms，排名$1.46\%$

Better

思路

还没看到更好的思路