验证二叉搜索树

Validate Binary Search Tree

问题：验证二叉搜索树

考察：树、深度优先搜索、二叉搜索树

来源：DSA Prep / Citadel

链接：https://leetcode.com/problems/validate-binary-search-tree

Problem: Validate Binary Search Tree

Patterns: Tree, Depth-First Search, Binary Search Tree

Recency: 2yr

Link: https://leetcode.com/problems/validate-binary-search-tree

Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/

解析

思路：递归时为每个节点传入允许的开区间上下界，左子树必须小于当前值，右子树必须大于当前值。也可中序遍历检查序列严格递增。

复杂度：时间 O(n)，递归栈 O(h)。