Java C++ 算法题解leetcode669修剪二叉搜索树示例

题目要求

思路一：模拟迭代

• 依次判断每个节点是否合法：
  • 首先找出结果的根，若原根小了就拉右边的过来，大了拉左边的过来做新根；
  • 然后分别判断左右子树的大小，由于二叉搜索树的性质，子树只需要判断一边就好：
    • 左子树判断是否>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;
    }
}

• 时间复杂度：o(n)
• 空间复杂度：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;
    }
};

• 时间复杂度：o(n)
• 空间复杂度：o(1)

思路二：递归

• 直接用当前函数递归修剪即可：
  • 当前值小了放右下（大）的值进去，剪掉当前和左边节点；
  • 当前值大了放左下（小）的值进去，剪掉当前和右边节点。
  • 然后递归掉下面所有节点。

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;
    }
}

• 时间复杂度：o(n)
• 空间复杂度：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;
    }
};

• 时间复杂度：o(n)
• 空间复杂度：o(1)，忽略递归的额外空间开销

rust

• 今天又见识到了新报错：already borrowed: borrowmuterror，不能把borrow的东西来回随便等，要搞临时中间变量，闭包要关好。

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)); // 要先拎出来
        root.as_ref().unwrap().borrow_mut().left = l;
        root.as_ref().unwrap().borrow_mut().right = r;
        root
    }
}

• 时间复杂度：o(n)
• 空间复杂度：o(1)，忽略递归的额外空间开销

以上就是java c++ 算法题解leetcode669修剪二叉搜索树的详细内容，更多关于java c++ 算法修剪二叉搜索树的资料请关注其它相关文章！