LeetCode //C - 669. Trim a Binary Search Tree

669. Trim a Binary Search Tree

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                            ,                            1                                       0                               4                                      ]                                  [1, 10^4]                     [1,104].
  
•                                         0                            <                            =                            N                            o                            d                            e                            .                            v                            a                            l                            <                            =                            1                                       0                               4                                            0 <= Node.val <= 10^4                     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                            <                            =                            l                            o                            w                            <                            =                            h                            i                            g                            h                            <                            =                            1                                       0                               4                                            0 <= low <= high <= 10^4                     0<=low<=high<=104
  

From: LeetCode
Link: 669. Trim a Binary Search Tree

---

Solution:

Ideas:

• If root->val < low, the current node and its left subtree are discarded (too small).
  
• If root->val > high, the current node and its right subtree are discarded (too big).
  
• Otherwise, recursively trim the left and right subtrees and return the current node.
  

Code:

1. /**
2. * Definition for a binary tree node.
3. * struct TreeNode {
4. *     int val;
5. *     struct TreeNode *left;
6. *     struct TreeNode *right;
7. * };
8. */
9. struct TreeNode* trimBST(struct TreeNode* root, int low, int high) {
10.     if (root == NULL)
11.         return NULL;
13.     // If the value is less than low, the entire left subtree can be ignored
14.     if (root->val < low)
15.         return trimBST(root->right, low, high);
17.     // If the value is greater than high, the entire right subtree can be ignored
18.     if (root->val > high)
19.         return trimBST(root->left, low, high);
21.     // Otherwise, recursively trim both subtrees
22.     root->left = trimBST(root->left, low, high);
23.     root->right = trimBST(root->right, low, high);
25.     return root;
26. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。