preorder - 给定一个数字列表，判断它是否可以表示二叉搜索树（BST）的前序遍历列表

Question

给定一个数字列表，确定它是否可以表示二叉搜索树（BST）的前序遍历列表。

public boolean isValid(int[] arr)
    {

        int root = arr[0];
        int i=1;

        while(  i< arr.length && root >arr[i])
        {
            i++;
        }

        for(;i<arr.length;i++)
        {
            if(arr[i] <root)
            {
                return false;
            }
        }   

        return true;
    }

上述功能适用于大多数情况，例如{3,4,5,1,2}, {3, 2, 1, 5, 4, 6}, {1,2,3}. 但它不适用于{1,3,4,2}.

任何人都可以帮我解决这个问题。

Answer 1

这个想法是列出你可以识别的超过 3 个元素的列表left，right并且root在 BST 中就像前三个元素一样。现在它是预购当且仅当left<=root<=right。现在root进入堆栈并取下一个 3 并应用相同的逻辑。

直到你有少于三个元素：

1. 两个元素成为left和root与规则left<=root
2. 一个元素只是一个root

在这两种情况下，您都必须放入root堆栈。

现在获取堆栈并应用相同的逻辑......直到堆栈中只有一个元素，这意味着它是预购 BST。

现在把它写成递归函数非常简单和有趣。