669. Trim a Binary Search Tree

系统管理员 2024-04-08 09:26 67阅读 0赞

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:**

![03d59e898f3d5ea934b8b0fcd50d7de0.jpeg][]

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

**Example 2:**

![cbfd72ac1dc280ff39bd04b93baa4277.jpeg][]

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

题目：给二叉搜索树剪枝，使得所有节点值都在\[low, high\]之间

思路：DFS。代码：

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

[03d59e898f3d5ea934b8b0fcd50d7de0.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/747eb05447794e41a50900079685a462.jpeg
[cbfd72ac1dc280ff39bd04b93baa4277.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/2d2f0486abea4f13902265e0106993e3.jpeg