Verify Preorder Array for Binary Search Tree | 书脊
给一个int的array, 问你这个array是不是一个bst的preorder.
用stack做preorder遍历"
如果当前元素大于stack里的元素, 证明我们在遍历一个node的右节点, 这时,因为是preorder, 说明左节点已经遍历过了, 所以我们要把stack中所有小于当前元素的节点pop出来,并且用low记录最后的一个. 如果当前元素比low小, 证明循序有错误, 因为low是左子树中最小的元素.
然后每次把当前node放入stack, 最后stack中有元素也不影响判断是不是preorder
Read full article from Verify Preorder Array for Binary Search Tree | 书脊
No comments:
Post a Comment