669.修剪二叉搜索樹

給你二叉搜索樹的根節(jié)點 root ，同時給定最小邊界low 和最大邊界 high。通過修剪二叉搜索樹，使得所有節(jié)點的值在[low, high]中。修剪樹 不應該 改變保留在樹中的元素的相對結構 (即，如果沒有被移除，原有的父代子代關系都應當保留)。 可以證明，存在 唯一的答案 。

所以結果應當返回修剪好的二叉搜索樹的新的根節(jié)點。注意，根節(jié)點可能會根據(jù)給定的邊界發(fā)生改變。

示例 1：

輸入：root = [1,0,2], low = 1, high = 2
輸出：[1,null,2]

示例 2：

輸入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
輸出：[3,2,null,1]

遞歸法

class Solution {
    TreeNode left, right;
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null)  return null;
        if (root.val < low) {
            left = trimBST(root.right, low, high);// 尋找符合區(qū)間[low, high]的節(jié)點
            return left;
        }
        if (root.val > high) {
            right = trimBST(root.left, low, high);// 尋找符合區(qū)間[low, high]的節(jié)點
            return right;
        }
        root.left = trimBST(root.left, low, high); // root->left接入符合條件的左孩子
        root.right = trimBST(root.right, low, high);// root->right接入符合條件的右孩子
        return root;
    }
}

總結

以上是生活随笔為你收集整理的31_修剪二叉搜索树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。