Java?C++?算法題解leetcode669修剪二叉搜索樹示例

更新時(shí)間：2022年09月14日 09:43:39 作者：AnjaVon

這篇文章主要為大家介紹了Java?C++?算法題解leetcode669修剪二叉搜索樹示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

題目要求

思路一：模擬迭代

依次判斷每個(gè)節(jié)點(diǎn)是否合法：
- 首先找出結(jié)果的根，若原根小了就拉右邊的過(guò)來(lái)，大了拉左邊的過(guò)來(lái)做新根；
- 然后分別判斷左右子樹的大小，由于二叉搜索樹的性質(zhì)，子樹只需要判斷一邊就好：
  - 左子樹判斷是否>low，合法就向左下走，不合法往右下；
  - 右子樹判斷是否<high，合法就向右下走，不合法往左下。

Java

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        while (root != null && (root.val < low || root.val > high)) // 確定原根是否合法
            root = root.val < low ? root.right : root.left;
        TreeNode res = root;
        while (root != null) {
            while (root.left != null && root.left.val < low)
                root.left = root.left.right;
            root = root.left;
        }
        root = res;
        while (root != null) {
            while (root.right != null && root.right.val > high)
                root.right = root.right.left;
            root = root.right;
        }
        return res;
    }
}

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)

C++

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        while (root != nullptr && (root->val < low || root->val > high)) // 確定原根是否合法
            root = root->val < low ? root->right : root->left;
        TreeNode* res = root;
        while (root != nullptr) {
            while (root->left != nullptr && root->left->val < low)
                root->left = root->left->right;
            root = root->left;
        }
        root = res;
        while (root != nullptr) {
            while (root->right != nullptr && root->right->val > high)
                root->right = root->right->left;
            root = root->right;
        }
        return res;
    }
};

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)

思路二：遞歸

直接用當(dāng)前函數(shù)遞歸修剪即可：
- 當(dāng)前值小了放右下（大）的值進(jìn)去，剪掉當(dāng)前和左邊節(jié)點(diǎn)；
- 當(dāng)前值大了放左下（?。┑闹颠M(jìn)去，剪掉當(dāng)前和右邊節(jié)點(diǎn)。
- 然后遞歸掉下面所有節(jié)點(diǎn)。

Java

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null)
            return null;
        if (root.val < low)
            return trimBST(root.right, low, high);
        else if (root.val > high)
            return trimBST(root.left, low, high);
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)，忽略遞歸的額外空間開銷

C++

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == nullptr)
            return nullptr;
        if (root->val < low)
            return trimBST(root->right, low, high);
        else if (root->val > high)
            return trimBST(root->left, low, high);
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        return root;
    }
};

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)，忽略遞歸的額外空間開銷

Rust

今天又見識(shí)到了新報(bào)錯(cuò)：already borrowed: BorrowMutError，不能把borrow的東西來(lái)回隨便等，要搞臨時(shí)中間變量，閉包要關(guān)好。

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn trim_bst(root: Option<Rc<RefCell<TreeNode>>>, low: i32, high: i32) -> Option<Rc<RefCell<TreeNode>>> {
        if  root.is_none() {
            return None;
        }
        if root.as_ref().unwrap().borrow().val < low {
            return Solution::trim_bst(root.as_ref().unwrap().borrow().right.clone(), low, high);
        }
        else if root.as_ref().unwrap().borrow().val > high {
            return Solution::trim_bst(root.as_ref().unwrap().borrow().left.clone(), low, high);
        }
        let (l, r) = (Solution::trim_bst(root.as_ref().unwrap().borrow().left.clone(), low, high), Solution::trim_bst(root.as_ref().unwrap().borrow().right.clone(), low, high)); // 要先拎出來(lái)
        root.as_ref().unwrap().borrow_mut().left = l;
        root.as_ref().unwrap().borrow_mut().right = r;
        root
    }
}