- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
中序遍历
二叉搜索树需要满足以下三个条件：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
- 二叉搜索树在中序遍历时得到的序列一定是升序的
- 进行中序遍历，判断当前节点是否大于前一个节点
- 如果比前一个大，说明满足，则继续遍历，否则直接返回 false
递归
constisValidBST=function(root){letprev=-Infinityletresult=truefunctioninorder(root){if(root===null)returninorder(root.left)if(root.val<=prev){result=falsereturn}prev=root.valinorder(root.right)}inorder(root)returnresult}
- 时间复杂度: O(n)
- 空间复杂度: O(n)
迭代
递归隐式地维护了一个栈，在迭代的时候我们需要显式地将这个栈模拟出来。
constisValidBST=function(root){conststack=[]letprev=-Infinitywhile(root||stack.length){while(root){stack.push(root)root=root.left}root=stack.pop()if(root.val<=prev){returnfalse}prev=root.valroot=root.right}returntrue}
- 时间复杂度: O(n)
- 空间复杂度: O(n)