*LeetCode-Verify Preorder Sequence in Binary Search Tree
812 ワード
build bst using traversalあれらの問題はまた一回見ます
stackを使うたびにleft subtreeすなわちnumで「stack topはpush大きくなったらずっとpopは大きくないことを知ってpushに入る」
しかしpopを記録する最後の数字はすでに遍歴した左子rootが彼より小さいことはできないので、intに記録するたびにこの記録と比較しなければならない.もし彼より小さいものが現れたらfalse
stackを使うたびにleft subtreeすなわちnumで「stack topはpush大きくなったらずっとpopは大きくないことを知ってpushに入る」
しかしpopを記録する最後の数字はすでに遍歴した左子rootが彼より小さいことはできないので、intに記録するたびにこの記録と比較しなければならない.もし彼より小さいものが現れたらfalse
public class Solution {
public boolean verifyPreorder(int[] preorder) {
Stack <Integer> stack = new Stack<Integer> ();
if ( preorder == null || preorder.length == 0 )
return true;
int low = Integer.MIN_VALUE;
for ( int num : preorder ) {
if ( num < low )
return false;
while ( !stack.isEmpty() && num > stack.peek() ) {
low = stack.pop();
}
stack.push ( num );
}
return true;
}
}