题目描述
实现一个函数,检查一棵二叉树是否为二叉搜索树。
示例 1:
输入: 2 / \ 1 3输出: true
示例 2:
输入: 5 / \ 1 4 / \ 3 6输出: false解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ,但是其右子节点值为 4 。
解法
方法一:递归
我们可以对二叉树进行递归中序遍历,如果遍历到的结果是严格升序的,那么这棵树就是一个二叉搜索树。
因此,我们使用一个变量 $\textit{prev}$ 来保存上一个遍历到的节点,初始时 $\textit{prev} = -\infty$,然后我们递归遍历左子树,如果左子树不是二叉搜索树,直接返回 $\text{False}$,否则判断当前节点的值是否大于 $\textit{prev}$,如果不是,返回 $\text{False}$,否则更新 $\textit{prev}$ 为当前节点的值,然后递归遍历右子树。
时间复杂度 $O(n)$,空间复杂度 $O(n)$。其中 $n$ 是二叉树的节点个数。
Python3 Java C++ Go TypeScript Rust JavaScript C# Swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution :
def isValidBST ( self , root : Optional [ TreeNode ]) -> bool :
def dfs ( root : Optional [ TreeNode ]) -> bool :
if root is None :
return True
if not dfs ( root . left ):
return False
nonlocal prev
if prev >= root . val :
return False
prev = root . val
return dfs ( root . right )
prev = - inf
return dfs ( root )
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 /**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private TreeNode prev ;
public boolean isValidBST ( TreeNode root ) {
return dfs ( root );
}
private boolean dfs ( TreeNode root ) {
if ( root == null ) {
return true ;
}
if ( ! dfs ( root . left )) {
return false ;
}
if ( prev != null && prev . val >= root . val ) {
return false ;
}
prev = root ;
return dfs ( root . right );
}
}
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 /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public :
bool isValidBST ( TreeNode * root ) {
TreeNode * prev = nullptr ;
function < bool ( TreeNode * ) > dfs = [ & ]( TreeNode * root ) {
if ( ! root ) {
return true ;
}
if ( ! dfs ( root -> left )) {
return false ;
}
if ( prev && prev -> val >= root -> val ) {
return false ;
}
prev = root ;
return dfs ( root -> right );
};
return dfs ( root );
}
};
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 /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isValidBST ( root * TreeNode ) bool {
var prev * TreeNode
var dfs func ( * TreeNode ) bool
dfs = func ( root * TreeNode ) bool {
if root == nil {
return true
}
if ! dfs ( root . Left ) {
return false
}
if prev != nil && prev . Val >= root . Val {
return false
}
prev = root
return dfs ( root . Right )
}
return dfs ( root )
}
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 /**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function isValidBST ( root : TreeNode | null ) : boolean {
let prev : TreeNode | null = null ;
const dfs = ( root : TreeNode | null ) : boolean => {
if ( ! root ) {
return true ;
}
if ( ! dfs ( root . left )) {
return false ;
}
if ( prev && prev . val >= root . val ) {
return false ;
}
prev = root ;
return dfs ( root . right );
};
return dfs ( root );
}
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 // 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 {
fn dfs ( root : & Option < Rc < RefCell < TreeNode >>> , prev : & mut Option < i32 > ) -> bool {
if root . is_none () {
return true ;
}
let root = root . as_ref (). unwrap (). borrow ();
if ! Self :: dfs ( & root . left , prev ) {
return false ;
}
if prev . is_some () && prev . unwrap () >= root . val {
return false ;
}
* prev = Some ( root . val );
Self :: dfs ( & root . right , prev )
}
pub fn is_valid_bst ( root : Option < Rc < RefCell < TreeNode >>> ) -> bool {
Self :: dfs ( & root , & mut None )
}
}
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 /**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isValidBST = function ( root ) {
let prev = null ;
const dfs = root => {
if ( ! root ) {
return true ;
}
if ( ! dfs ( root . left )) {
return false ;
}
if ( prev && prev . val >= root . val ) {
return false ;
}
prev = root ;
return dfs ( root . right );
};
return dfs ( root );
};
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 /**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
private TreeNode prev ;
public bool IsValidBST ( TreeNode root ) {
return dfs ( root );
}
private bool dfs ( TreeNode root ) {
if ( root == null ) {
return true ;
}
if ( ! dfs ( root . left )) {
return false ;
}
if ( prev != null && prev . val >= root . val ) {
return false ;
}
prev = root ;
return dfs ( root . right );
}
}
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 /* class TreeNode {
* var val: Int
* var left: TreeNode?
* var right: TreeNode?
*
* init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* }
* }
*/
class Solution {
private var prev : TreeNode ?
func isValidBST ( _ root : TreeNode ?) -> Bool {
return dfs ( root )
}
private func dfs ( _ root : TreeNode ?) -> Bool {
guard let root = root else {
return true
}
if ! dfs ( root . left ) {
return false
}
if let prev = prev , prev . val >= root . val {
return false
}
prev = root
return dfs ( root . right )
}
}