1
2

输入：root = [2,1,3]
输出：true

1
2
3

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

// @lc code=start
// 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::cell::RefCell;
use std::rc::Rc;
impl Solution {
    /// ## 解题思路
    /// - 递归
    /// 1. bst合法的条件:
    ///    a. 空树合法;
    ///    b. 左子树为合法bst && 父节点值>左子树节点值.max();
    ///    c. 右子树为合法bst && 父节点值<右子树节点值.min();
    pub fn is_valid_bst(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
        fn is_valid(
            root: Option<Rc<RefCell<TreeNode>>>,
            upper: Option<i32>,
            lower: Option<i32>,
        ) -> bool {
            match root {
                None => return true,
                Some(root) => {
                    (lower.is_none() || root.borrow().val > lower.unwrap())
                        && (upper.is_none() || root.borrow().val < upper.unwrap())
                        && is_valid(
                            root.borrow().left.clone(),
                            Some(root.borrow().val),
                            lower.clone(),
                        )
                        && is_valid(
                            root.borrow().right.clone(),
                            upper.clone(),
                            Some(root.borrow().val),
                        )
                }
            }
        }

        is_valid(root, None, None)
    }
}
// @lc code=end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    /*
    ## 解题思路
    * 递归法：
    *   有效二叉树条件：
    *   1. 空树是一个有效的二叉搜索树；
    *   2. 如果存在左子树，则同时满足以下两个条件：
    *       2.1 根节点val > 左子树的最大节点值；
    *       2.2 左子树也是一颗有效二叉搜索树；
    *   3. 如果存在右子树，同时满足：
    *       3.1 根节点val < 右子树最小节点值；
    *       3.2 右子树也是一颗有效二叉搜索树；
    */
    bool isValidBST(TreeNode* root) {
        return isValid(root, NULL, NULL);
    }

    // 以root为根，lower为上限， upper为上限子树是否为有效二叉搜索树
    bool isValid(TreeNode* root, int* lower, int* upper) {
        if (!root) return true;

        if (upper && root->val >= *upper) return false;
        if (lower && root->val <= *lower) return false;

        return isValid(root->left, lower, &(root->val))
            && isValid(root->right, &(root->val), upper);

    }
};