*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
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;
    }
}