聖地亞歌

Leetcode P0255"Verify Preorder Sequence in Binary Search Tree" 题解

2021/04/11 Leetcode

博文中会简要介绍Leetcode P0255题目分析及解题思路。

“Verify Preorder Sequence in Binary Search Tree”是一道中等难度的题目，这道题有两种思路，第一种思路是利用前序遍历和二叉搜索树的特性，用栈来记录前序遍历到每个结点时该结点在栈中的位置，也即结点在之后遍历中出现的顺序；第二种思路则是用中序遍历和前序遍历构造二叉搜索树的方法，模拟一遍二叉搜索树的构造过程，如果模拟不成功则说明前序遍历是有问题的。

Given an array of unique integers preorder, return true if it is the correct preorder traversal sequence of a binary search tree.

先简单讲解第一种思路。我们模拟二叉搜索树的前序遍历，利用栈来保存结点，如果下一个结点的值小于栈顶结点的值，则我们仍位于所有栈内结点的左侧子树中，因此只需将新的结点值入栈即可；反之，弹出所有较小的祖先值直到栈顶的结点值大于当前结点值，此时我们将位于上一个弹出的栈顶结点的右侧子树中，也是应当存在当前结点的子树。另外，将最后一个弹出的值作为下限，因为位于其正确的子树中意味着我们不应当再遇到更小的值。

以下是Java的题解代码实现。

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        int low = Integer.MIN_VALUE;
        Deque<Integer> path = new LinkedList<>();
        for (int p: preorder) {
            if (p < low)
                return false;
            
            while (!path.isEmpty() && p > path.peekFirst()) {
                low = path.pollFirst();
            }
            
            path.offerFirst(p);
        }
        
        return true;
    }
}

第二种思路比较直接。首先对给定的前序遍历结果排序，由于是二叉搜索树，所以从小到大排序后得到的就是某个二叉搜索树的中序遍历结果。然后利用前序遍历和中序遍历模拟一遍树的构造过程，如果发现不能构造则说明给定的前序遍历结果存在问题。

以下是第二种思路的Java题解代码实现。

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        int N = preorder.length;
        // Obtain the inorder of the potential binary search tree
        int[] inorder = Arrays.copyOf(preorder, N);
        Arrays.sort(inorder);
        
        this.preorder = preorder;
        this.inorder = inorder;
        return this.dfs(0, 0, N-1);
    }
    
    private int[] preorder, inorder;
    
    private boolean dfs(int itr, int beg, int end) {
        if (beg > end)
            return true;
        
        int mid = -1;
        for (int idx=beg; idx<=end; ++idx) {
            if (this.preorder[itr] == this.inorder[idx]) {
                mid = idx;
            }
        }
        // Cannot find the root located in the right position
        if (mid == -1)
            return false;
        
        return (this.dfs(itr+1, beg, mid-1) && this.dfs(itr+mid-beg+1, mid+1, end));
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        int low = INT_MIN;
        stack<int> path;
        for (int p: preorder) {
            if (p < low)
                return false;
            
            while (!path.empty() && p > path.top()) {
                low = path.top();
                path.pop();
            }
            
            path.push(p);
        }
        
        return true;
    }
};

Search

    Table of Contents