LeetCode 255. Verify Preorder Sequence in Binary Search Tree（檢查二叉搜尋樹的前序周遊）

原題網址：https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Follow up:

Could you do it using only constant space complexity?

方法一：分治政策，根據二叉搜尋樹的特性，分别尋找比對目前節點的左子樹和右子樹。需要使用遞歸。

public class Solution {
    private int range(int[] preorder, int from, int min, int max) {
        if (from == preorder.length) return from;
        if (preorder[from] < min || preorder[from] > max) return from;
        int small = range(preorder, from+1, min, preorder[from]-1);
        int great = range(preorder, small, preorder[from]+1, max);
        return great;
    }
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length <= 1) return true;
        int small = range(preorder, 1, Integer.MIN_VALUE, preorder[0]-1);
        int great = range(preorder, small, preorder[0]+1, Integer.MAX_VALUE);
        return great == preorder.length;
    }
}
           

代碼參考：http://my.oschina.net/u/922297/blog/498356

方法二：前序周遊的特點，是節點周遊先減後增，減的時候可以随意減少，但開始增加的時候，表明正在右子樹，則往後的任何值都不能小于目前節點的值。

public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        Stack<Integer> stack = new Stack<>();
        int min = Integer.MIN_VALUE;
        for(int node: preorder) {
            if (node < min) return false;
            while (!stack.isEmpty() && stack.peek() < node) min = stack.pop();
            stack.push(node);
        }
        return true;
    }
}
           

如果允許我們修改來源資料的話，就可以使用preorder作為棧，而不需要額外配置設定空間：

public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        int size = 0;
        int min = Integer.MIN_VALUE;
        for(int node: preorder) {
            if (node < min) return false;
            while (size > 0 && preorder[size-1] < node) min = preorder[--size];
            preorder[size++] = node;
        }
        return true;
    }
}
           

但原理是一樣的。

參考文章：https://segmentfault.com/a/1190000003874375