题目描述#

给你一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树。

有效 BST 要求：左子树所有节点严格小于当前节点，右子树所有节点严格大于当前节点，且所有子树也满足此性质。

思路#

BST 的中序遍历结果是严格递增序列，因此只需对树做中序遍历，同时用 pre 记录上一个访问节点的值，若当前节点值 ≤ pre，说明不满足严格递增，直接返回 false。

pre 初始化为 math.MinInt，表示还没有访问过任何节点。遍历按"左→中→右"的顺序进行，只要在访问"中"节点时发现 node.Val <= pre，就可以提前终止。

以树 [5, 1, 8, nil, nil, 7, 9] 为例，递归展开过程如下：

dfs(5)
├── dfs(1)              // 先走左
│   ├── dfs(nil)        // 1的左子树为空，return true
│   ├── 1 > MinInt ✅   pre = 1
│   └── dfs(nil)        // 1的右子树为空，return true
│   return true
├── 5 > 1 ✅            pre = 5
└── dfs(8)              // 再走右
    ├── dfs(7)          // 先走左
    │   ├── dfs(nil)    // return true
    │   ├── 7 > 5 ✅    pre = 7
    │   └── dfs(nil)    // return true
    │   return true
    ├── 8 > 7 ✅        pre = 8
    └── dfs(9)          // 再走右
        ├── dfs(nil)    // return true
        ├── 9 > 8 ✅    pre = 9
        └── dfs(nil)    // return true
        return true
    return true
return true

知识边界#

• BST 中序遍历得到严格递增序列，是验证、查询 BST 题目的核心性质
• pre 初始化为 math.MinInt 而非 math.MinInt / 2，此处只做比较不做减法，不会溢出
• 提前返回 false 的位置在"先左后中"之间，一旦左子树返回 false 立即终止，不再遍历右子树

代码#

import "math"

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    pre := math.MinInt
    var dfs func(*TreeNode) bool
    dfs = func(node *TreeNode) bool {
        if node == nil {
            return true
        }
        if dfs(node.Left) == false {
            return false
        }
        if node.Val <= pre {
            return false
        }
        pre = node.Val
        return dfs(node.Right)
    }

    return dfs(root)
}