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:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Input: 1 / \ 0 2 L = 1 R = 2 Output: 1 \ 2 |
Example 2:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
Input: 3 / \ 0 4 \ 2 / 1 L = 1 R = 3 Output: 3 / 2 / 1 |
This problem can be solved with recursion
There 3 cases in total depends on the root value and L, R
Time complexity: O(n)
Space complexity: O(1)
Solution:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: // No cleanup -> memory leak TreeNode* trimBST(TreeNode* root, int L, int R) { if(!root) return nullptr; // val not in range, return the left/right subtrees if(root->val < L) return trimBST(root->right, L, R); if(root->val > R) return trimBST(root->left, L, R); // val in [L, R], recusively trim left/right subtrees root->left = trimBST(root->left, L, R); root->right = trimBST(root->right, L, R); return root; } }; |
The previous solution has potential memory leak for languages without garbage collection.
Here’s the full program to delete trimmed nodes.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
// Author: Huahua #include <iostream> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { public: // With cleanup -> no memory leak TreeNode*& trimBST(TreeNode*& root, int L, int R) { if(!root) return root; if(root->val < L) { auto& result = trimBST(root->right, L, R); deleteTree(root->left); delete root; root=nullptr; return result; } else if(root->val > R) { auto& result = trimBST(root->left, L, R); deleteTree(root->right); delete root; root=nullptr; return result; } else { // recusively trim left/right subtrees root->left = trimBST(root->left, L, R); root->right = trimBST(root->right, L, R); return root; } } void deleteTree(TreeNode* &root) { if(!root) return; deleteTree(root->left); deleteTree(root->right); delete root; root=nullptr; } }; void PrintTree(TreeNode* root) { if(!root) { cout<<"null "; return; }; if(!root->left && !root->right) { cout<<root->val<<" "; } else { cout<<root->val<<" "; PrintTree(root->left); PrintTree(root->right); } } int main() { TreeNode* root=new TreeNode(2); root->left=new TreeNode(1); root->right=new TreeNode(3); PrintTree(root); std::cout<<std::endl; TreeNode* t = Solution().trimBST(root, 3, 4); PrintTree(t); std::cout<<std::endl; // Original root was deleted PrintTree(root); std::cout<<std::endl; return 0; } |
Example output
|
1 2 3 |
2 1 3 3 null |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment