抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

18|面试题:验证二叉搜索树

二叉搜索树概念

⼆叉搜索树(英语:Binary Search Tree),也称⼆叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sorted binary tree),是指一棵空树或者具有下列列性质的⼆叉树:

  1. 若任意节点的左⼦树不空,则左⼦树上所有结点的值均小于它的根结点的值;
  2. 若任意节点的右⼦树不空,则右⼦树上所有结点的值均大于它的根结点的值;
  3. 任意节点的左、右⼦子树也分别为二叉查找树。

题目:

98. 验证二叉搜索树

解决方案一:中序遍历结果为升序则为二叉查找树,遍历结果是否为升序时仅需保留前一个元素即可。时间复杂度O(N)。

前置知识:

  1. 前序遍历(Pre-order):根 – 左 – 右
  2. 中序遍历(In-order):左 – 根 – 右
  3. 后序遍历(Post-order):左 – 右- 根

规律:前中后指根的位置,左右顺序不变。

解决方案二:递归,如下(Kotlin 版):

class Solution {

fun isValidBST(root: TreeNode?): Boolean {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE)
}

fun isValidBST(root: TreeNode?, low: Long, high: Long): Boolean{
root?:return true
if(root.`val`<=low) return false
if(root.`val`>=high) return false
return isValidBST(root.left, low, root.`val`.toLong()) && isValidBST(root.right, root.`val`.toLong(), high)
}

}

采用递归方案,左子树一定比根节点小,右子树一定比根节点大。

框架,找左子树最大值,右子树最小值:

isValidBST(* , min , max)
 isValidBST(node.left)  -> max
 isValidBST(node.right) -> min
 满足 max < root && min >root ,持续递归即可。

时间复杂度O(N)。


0条评论

发表评论