0%

LeetCode 669. Trim a Binary Search Tree

Posted on In

题目

原题在此
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]

Example 3:
Input: root = [1], low = 1, high = 2
Output: [1]

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

Example 5:
Input: root = [1,null,2], low = 2, high = 4
Output: [2]

Constraints:

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

解析

根据题意有如下关系:

  1. 当前节点val < low时, 此节点的左子树全部小于low. 换言之, 若root -> left -> val < low, root -> left = root -> left -> right.
  2. 同理val > high时, 右子树全部大于high. 既若root -> right -> val > high, root -> right = root -> right -> left
  3. 传入的root也有可能不在区间内, 要先根据上述关系找到return的root.

代码

iterative

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
/**
 * 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) {
        if(!root) return root;
        while(root -> val < low || root -> val > high) {
            if(root -> val < low ) root = root -> right;
            if(root -> val > high) root = root -> left;
        }
        TreeNode* tmp = root;
        while(tmp) {
            while(tmp -> left && tmp -> left -> val < low) tmp -> left = tmp -> left -> right;
            tmp = tmp -> left;
        }
        
        tmp = root;
        while(tmp) {
            while(tmp -> right && tmp -> right -> val > high) tmp -> right = tmp -> right -> left;
            tmp = tmp -> right;
        }
        return root;
    }
};

recursive

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int L, int R) {
        if (root == NULL) return NULL;
        if (root->val < L) return trimBST(root->right, L, R);
        if (root->val > R) return trimBST(root->left, L, R);
        root->left = trimBST(root->left, L, R);
        root->right = trimBST(root->right, L, R);
        return root;
    }
};