描述
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- Both the left and right subtrees must also be binary search trees.
分析
判断一个二叉树是否为二分查找树。
需要注意的是,如果是左子树,是左子树的所有节点都比根节点小,而非只是左孩子比其小。
解决方案1(C++)
遍历时记录当前节点所允许的最大值、最小值,时间复杂度O(n),空间复杂度O(logn)
1 | /** |