98. 验证二叉搜索树

题目描述

输入二叉树的根节点 root。二叉树按层序写成数组，空位置用 null 表示，例如 [3,9,20,null,null,15,7]。

判断它是不是一棵合法的二叉搜索树。合法的条件是：对每个节点，左子树里的所有值都严格小于它，右子树里的所有值都严格大于它，并且左右子树本身也合法。

合法返回 true，否则返回 false。

示例 1

输入：root = [2,1,3]
输出：true

解释：1 在左、比 2 小；3 在右、比 2 大。

示例 2

输入：root = [5,1,4,null,null,3,6]
输出：false

解释：根为 5，右孩子却是 4，不满足条件。

数据范围

节点数在 [1, 10^4] 范围内。
-2^31 <= Node.val <= 2^31 - 1

解题思路：递归（传递上下界）

递归传递严格上下界，左子树缩小上界，右子树提高下界。

为什么正确

每个节点都必须落在所有祖先共同约束出的开区间内。

复杂度分析

时间 O(n)，递归栈 O(h)；h 为树高，最坏可为 n；Python 递归受解释器递归深度限制，深链树应改用显式栈。

易错点

仅比较直接孩子会遗漏祖先约束；重复值也不符合本题严格定义。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def isValidBST(self, root):
        def check(node, low, high):
            if not node:
                return True
            if not low < node.val < high:
                return False
            return (check(node.left, low, node.val) and
                    check(node.right, node.val, high))
        return check(root, float('-inf'), float('inf'))

class Solution {
    public boolean isValidBST(TreeNode root) {
        return check(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean check(TreeNode node, long low, long high) {
        if (node == null) {
            return true;
        }
        if (!(low < node.val && node.val < high)) {
            return false;
        }
        return check(node.left, low, node.val) &&
               check(node.right, node.val, high);
    }
}

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return check(root, LLONG_MIN, LLONG_MAX);
    }

    bool check(TreeNode* node, long long low, long long high) {
        if (!node) {
            return true;
        }
        if (!(low < node->val && node->val < high)) {
            return false;
        }
        return check(node->left, low, node->val) &&
               check(node->right, node->val, high);
    }
};

func isValidBST(root *TreeNode) bool {
	var check func(node *TreeNode, low, high int) bool
	check = func(node *TreeNode, low, high int) bool {
		if node == nil {
			return true
		}
		if !(low < node.Val && node.Val < high) {
			return false
		}
		return check(node.Left, low, node.Val) &&
			check(node.Right, node.Val, high)
	}
	return check(root, math.MinInt64, math.MaxInt64)
}

var isValidBST = function(root) {
    const check = (node, low, high) => {
        if (!node) {
            return true;
        }
        if (!(low < node.val && node.val < high)) {
            return false;
        }
        return check(node.left, low, node.val) &&
               check(node.right, node.val, high);
    };
    return check(root, -Infinity, Infinity);
};

function isValidBST(root: TreeNode | null): boolean {
    const check = (node: TreeNode | null, low: number, high: number): boolean => {
        if (!node) {
            return true;
        }
        if (!(low < node.val && node.val < high)) {
            return false;
        }
        return check(node.left, low, node.val) &&
               check(node.right, node.val, high);
    };
    return check(root, -Infinity, Infinity);
}

载入编辑器，自己跑一遍 →

其他解法

递归上下界把祖先带来的约束向下传递，直接检查定义；中序遍历利用“BST 中序有序”的性质，只需比较相邻元素。两者复杂度相同。

解法 2：中序遍历时间 O(n)，空间 O(n)

二叉搜索树有一个等价判定：中序遍历得到的序列严格递增。用显式栈做中序遍历，记住上一个访问的值 prev，一旦当前值小于等于 prev 就不是合法的 BST。

把“全局约束”转化为“相邻两个元素的比较”，很直观，还能在发现第一个逆序时提前退出。prev 的初始值要小于所有可能的节点值，C++/Java 需要用 64 位最小值。

class Solution:
    def isValidBST(self, root):
        stack = []
        prev = None
        cur = root
        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            # BST 的中序遍历必须严格递增
            if prev is not None and cur.val <= prev:
                return False
            prev = cur.val
            cur = cur.right
        return True

class Solution {
    public boolean isValidBST(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        long prev = Long.MIN_VALUE;
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if (cur.val <= prev) return false;
            prev = cur.val;
            cur = cur.right;
        }
        return true;
    }
}

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        vector<TreeNode*> stack;
        long long prev = LLONG_MIN;
        TreeNode* cur = root;
        while (cur || !stack.empty()) {
            while (cur) {
                stack.push_back(cur);
                cur = cur->left;
            }
            cur = stack.back();
            stack.pop_back();
            if (cur->val <= prev) return false;
            prev = cur->val;
            cur = cur->right;
        }
        return true;
    }
};

func isValidBST(root *TreeNode) bool {
	stack := []*TreeNode{}
	hasPrev, prev := false, 0
	cur := root
	for cur != nil || len(stack) > 0 {
		for cur != nil {
			stack = append(stack, cur)
			cur = cur.Left
		}
		cur = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if hasPrev && cur.Val <= prev {
			return false
		}
		hasPrev, prev = true, cur.Val
		cur = cur.Right
	}
	return true
}

var isValidBST = function(root) {
    const stack = [];
    let prev = -Infinity;
    let cur = root;
    while (cur || stack.length) {
        while (cur) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        if (cur.val <= prev) return false;
        prev = cur.val;
        cur = cur.right;
    }
    return true;
};

function isValidBST(root: TreeNode | null): boolean {
    const stack: TreeNode[] = [];
    let prev = -Infinity;
    let cur = root;
    while (cur || stack.length) {
        while (cur) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop()!;
        if (cur.val <= prev) return false;
        prev = cur.val;
        cur = cur.right;
    }
    return true;
}

二叉树专题的其他题目

查看二叉树全部题目 →