题解 | #判断是不是二叉搜索树#

问：怎么确定三个小问题顺序的？为什么采用中序遍历？

答：由函数功能和确定顺序两方面确定。

一、主语：函数功能

• 搜索树定义：我这个节点大于左子树全部节点，右子树全部节点大于我。
• 我这个函数要解决的问题：我这一整棵树是不是搜索树。
• 划分成三个顺序未知的小问题：
• 1.我这个节点是否符合大于左子树全部节点，小于右子树全部节点；
• 2.左子树是不是搜索树（调自己）；
• 3.右子树是不是搜索树（调自己）。

二、主语：确定顺序

• 搜索树特点：中序遍历时递增。即中序遍历时，我这个节点大于左子树的尾节点，右子树第一个节点大于我。
• 借助搜索树的特点，如果用中序遍历，三个小问题的顺序变为：左子树是不是搜索树，我这个节点符不符合条件，右子树是不是搜索树。那么小问题1便简化为了“我是否大于左子树尾节点，右子树第一个节点是否大于我“。

package main
//import "fmt"
import . "nc_tools"

var pre *TreeNode
func isValidBST( root *TreeNode ) bool {
    // write code here
    if root == nil {
        return true
    }
    if !isValidBST(root.Left) {
        return false
    }
    if pre == nil {
        pre = root
    } else {
        if root.Val<=pre.Val {
            return false
        }
        pre = root
    }
    return isValidBST(root.Right)
}