98. Validate Binary Search Tree Medium

1/**
2 * [98] Validate Binary Search Tree
3 *
4 * Given the root of a binary tree, determine if it is a valid binary search tree (BST).
5 * A valid BST is defined as follows:
6 *
7 * The left subtree of a node contains only nodes with keys less than the node's key.
8 * The right subtree of a node contains only nodes with keys greater than the node's key.
9 * Both the left and right subtrees must also be binary search trees.
10 *
11 *  
12 * Example 1:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2020/12/01/tree1.jpg" style="width: 302px; height: 182px;" />
14 * Input: root = [2,1,3]
15 * Output: true
16 *
17 * Example 2:
18 * <img alt="" src="https://assets.leetcode.com/uploads/2020/12/01/tree2.jpg" style="width: 422px; height: 292px;" />
19 * Input: root = [5,1,4,null,null,3,6]
20 * Output: false
21 * Explanation: The root node's value is 5 but its right child's value is 4.
22 *
23 *  
24 * Constraints:
25 *
26 * The number of nodes in the tree is in the range [1, 10^4].
27 * -2^31 <= Node.val <= 2^31 - 1
28 *
29 */
30pub struct Solution {}
31#[allow(unused_imports)]
32use crate::util::tree::{to_tree, TreeNode};
33
34// problem: https://leetcode.com/problems/validate-binary-search-tree/
35// discuss: https://leetcode.com/problems/validate-binary-search-tree/discuss/?currentPage=1&orderBy=most_votes&query=
36
37// submission codes start here
38
39// Definition for a binary tree node.
40// #[derive(Debug, PartialEq, Eq)]
41// pub struct TreeNode {
42//   pub val: i32,
43//   pub left: Option<Rc<RefCell<TreeNode>>>,
44//   pub right: Option<Rc<RefCell<TreeNode>>>,
45// }
46//
47// impl TreeNode {
48//   #[inline]
49//   pub fn new(val: i32) -> Self {
50//     TreeNode {
51//       val,
52//       left: None,
53//       right: None
54//     }
55//   }
56// }
57use std::cell::RefCell;
58use std::rc::Rc;
59type Node = Option<Rc<RefCell<TreeNode>>>;
60impl Solution {
61    pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
62        Self::is_valid(&root, i64::MAX, i64::MIN)
63    }
64
65    fn is_valid(node: &Node, max: i64, min: i64) -> bool {
66        if let Some(n) = node {
67            let nf = n.as_ref().borrow();
68            return max > nf.val as i64
69                && min < nf.val as i64
70                && Self::is_valid(&nf.right, max, nf.val as i64)
71                && Self::is_valid(&nf.left, nf.val as i64, min);
72        } else {
73            return true;
74        }
75    }
76}
77
78// submission codes end
79
80#[cfg(test)]
81mod tests {
82    use super::*;
83    use crate::tree;
84
85    #[test]
86    fn test_98() {
87        assert!(!Solution::is_valid_bst(tree![5,1,4,null,null,3,6]));
88        assert!(Solution::is_valid_bst(tree![2,1,3]));
89    }
90}
91