判断是不是二叉搜索树

发表于

描述
给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树。

二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点。

题解
二叉搜索树的特性就是中序遍历是递增序。既然是判断是否是二叉搜索树，那我们可以使用中序递归遍历。只要之前的节点是二叉树搜索树，那么如果当前的节点小于上一个节点值那么就可以向下判断

  • 前置节点默认是 -1<<(32-1)
  • 首先递归到最左
  • 往后遍历整棵树，依次连接pre与当前节点，并更新pre
  • 左子树如果不是二叉搜索树返回false
  • 判断当前节点是不是小于前置节点，更新前置节点
  • 递归右子树
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
package main

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}


/**
 *
 *
 * @param root TreeNode类
 * @return bool布尔型
 */
var pre = -1 << (32 - 1)
func isValidBST( root *TreeNode ) bool {
    // write code here
    if root == nil {
        return true
    }
    if !isValidBST(root.Left) {
        return false
    }
    if (root.Val < pre) {
        return false
    }
    pre = root.Val
    return isValidBST(root.Right)
}