[−][src]Function leetcode_for_rust::cd0098_validate_binary_search_tree::is_valid_bst
pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool
Solutions
Approach 1: Recursion
-
Time complexity: O(n)
-
Space complexity: O(n)
-
Runtime: 4 ms
-
Memory: 3.4 MB
// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: Option<Rc<RefCell<TreeNode>>>, // pub right: Option<Rc<RefCell<TreeNode>>>, // } // // impl TreeNode { // #[inline] // pub fn new(val: i32) -> Self { // TreeNode { // val, // left: None, // right: None // } // } // } use std::rc::Rc; use std::cell::RefCell; impl Solution { pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool { fn valid(root: &Option<Rc<RefCell<TreeNode>>>, min_limit: Option<i32>, max_limit: Option<i32>) -> bool { match root { Some(node) => { let node = node.borrow(); if let Some(v) = min_limit { if node.val <= v { return false; } } if let Some(v) = max_limit { if node.val >= v { return false; } } return valid(&node.left, min_limit, Some(node.val)) && valid(&node.right, Some(node.val), max_limit); }, _ => { true } } // if let Some(n) = node { // let n = n.borrow(); // // if let Some(v) = min_limit { // if n.val <= v { return false; } // } // if let Some(v) = max_limit { // if n.val >= v { return false; } // } // return valid(&n.left, min_limit, Some(n.val)) && valid(&n.right, Some(n.val), max_limit); // } else { // true // } } valid(&root, None, None) } }
Approach 2: inorder
-
Time complexity: O(n)
-
Space complexity: O(n)
-
Runtime: 4 ms
-
Memory: 3.8 MB
// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: Option<Rc<RefCell<TreeNode>>>, // pub right: Option<Rc<RefCell<TreeNode>>>, // } // // impl TreeNode { // #[inline] // pub fn new(val: i32) -> Self { // TreeNode { // val, // left: None, // right: None // } // } // } use std::rc::Rc; use std::cell::RefCell; impl Solution { pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool { fn inorder(root: &Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> { let mut result = vec![]; if let Some(node) = root { let mut left = inorder(&node.borrow().left); let mut right = inorder(&node.borrow().right); result.append(&mut left); result.push(node.borrow().val); result.append(&mut right); } result } let result = inorder(&root); for i in 1..result.len() { if result[i] <= result[i-1] { return false; } } true } }