二叉搜索树概念

⼆叉搜索树(英语:Binary Search Tree)，也称⼆叉搜索树、有序二叉树(英语:ordered binary tree)，排序二叉树(英语:sorted binary tree)，是指一棵空树或者具有下列列性质的⼆叉树:

1. 若任意节点的左⼦树不空，则左⼦树上所有结点的值均小于它的根结点的值;
2. 若任意节点的右⼦树不空，则右⼦树上所有结点的值均大于它的根结点的值;
3. 任意节点的左、右⼦子树也分别为二叉查找树。

题目：

98. 验证二叉搜索树

解决方案一：中序遍历结果为升序则为二叉查找树，遍历结果是否为升序时仅需保留前一个元素即可。时间复杂度O(N)。

前置知识：

1. 前序遍历(Pre-order)：根 – 左 – 右
2. 中序遍历(In-order)：左 – 根 – 右
3. 后序遍历(Post-order)：左 – 右- 根

规律：前中后指根的位置，左右顺序不变。

解决方案二：递归，如下（Kotlin 版）：

class Solution {

    fun isValidBST(root: TreeNode?): Boolean {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE)
    }

    fun isValidBST(root: TreeNode?, low: Long, high: Long): Boolean{
        root?:return true
        if(root.`val`<=low) return false
        if(root.`val`>=high) return false
        return isValidBST(root.left, low, root.`val`.toLong()) && isValidBST(root.right, root.`val`.toLong(), high)
    }

}

采用递归方案，左子树一定比根节点小，右子树一定比根节点大。

框架，找左子树最大值，右子树最小值：

isValidBST（* , min , max）
 isValidBST(node.left)  -> max
 isValidBST(node.right) -> min
 满足 max < root && min >root ，持续递归即可。

时间复杂度O(N)。