[Leetcode] Verify Preorder Sequence in Binary Sear

未东兴发布于2019-08-14 12:46 / 2238人阅读

摘要：如果继续降序，说明又向左走了，这样等到下次向右走得时候也要再次更新最小值。这样，序列无效的条件就是违反了这个最小值的限定。我们同样可以用本题的方法解，不过是从数组的后面向前面遍历，因为在后面了。栈的增长方向也是从高向低了。

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?

栈法 复杂度

时间 O(N) 空间 O(N)

思路

二叉搜索树先序遍历序列的特点是降序的部分一定是向左走的，一旦开始升序说明开始向右走了，则上一个降序的点则限定了后面的数的最小值。如果继续降序，说明又向左走了，这样等到下次向右走得时候也要再次更新最小值。

如这个例子，我们在10的位置是没有最小值限定的，然后降序走到5，依然没有最小值，降序走到2，依然没有，然后开始升序了，遇到6，这时候之后的数字一定大于2，同时也大于5，所以最小值更新为之前遍历过的，且比当前数稍微小一点的那个数。这里我们可以用一个栈来暂存之前的路径，所以升序时就是将栈中元素不断pop出来直到栈顶大于当前数，而最小值就是最后一个pop出来的数，最后再把该数push进去。对于降序的时候，直接向里面push就行了。这样，序列无效的条件就是违反了这个最小值的限定。

代码

public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        Stack stk = new Stack();
        // 初始化最小值为最小整数
        int min = Integer.MIN_VALUE;
        for(int num : preorder){
            // 违反最小值限定则是无效的
            if(num < min) return false;
            // 将路径中所有小于当前的数pop出来并更新最小值
            while(!stk.isEmpty() && num > stk.peek()){
                min = stk.pop();
            }
            // 将当前值push进去
            stk.push(num);
        }
        return true;
    }
}

指针模拟栈法 复杂度

时间 O(N) 空间 O(N)

思路

同样是看这个例子，我们序列是[10, 5, 2, 6, 12]，如果用栈的话，遍历序列到第n个数时，栈中的情况是这样的：

可见我们栈的大小是不会超过我们当前遍历的数的位置的，所以我们大可以用该序列的之前遍历过的部分来当做我们的栈。这里用一个i指针标记栈顶。

注意

这里栈顶指针应初始化为-1，这样栈第一个元素加入时，i++后不会超界

代码

public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        // 用i标记栈顶
        int i = -1, min = Integer.MIN_VALUE;
        for(int num : preorder){
            if(num < min) return false;
            // 同样的解法，但是复用了数组作为栈，每pop一次相当于i--
            while(i >= 0 && num > preorder[i]){
                min = preorder[i--];
            }
            // push相当于i++
            preorder[++i] = num;
        }
        return true;
    }
}

后续 Follow Up

Q：如何验证中序序列？
A：中序序列是有序的，只要验证其是否升序的就行了。

Q：如何验证后序序列？
A：后序序列的顺序是left - right - root，而先序的顺序是root - left - right。我们同样可以用本题的方法解，不过是从数组的后面向前面遍历，因为root在后面了。而且因为从后往前看是先遇到right再遇到left，所以我们要记录的是限定的最大值，而不再是最小值，栈pop的条件也变成pop所有比当前数大得数。栈的增长方向也是从高向低了。

    public boolean IsValidPostOrderBst(int[] nums)
    {
        int i = nums.length;
        int max = Integer.MAX_VALUE;
        for (int j = nums.length - 1; j >= 0; j--)
        {
            if (nums[j] > max) return false;
            while (i <= nums.length - 1 && nums[j] > nums[i])
                max = nums[i++];
            nums[--i] = nums[j];
        }
        return true;
    }

云服务器 GPU云服务器 Sequence Preorder verify LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64693.html

leetcode331. Verify Preorder Serialization of a Bi

摘要：如果我们从右往左看先序遍历，就知道后两个节点如果遇到第三个节点，则该节点就应当是这两个节点的父节点。如果在遍历的过程中根节点数量小于，则说明这棵树有问题。而如果遍历结束之后，剩下的根节点数不等于，也说明这个先序遍历存在问题。题目要求 One way to serialize a binary tree is to use pre-order traversal. When we en...

weapon 2019-08-16 13:50 评论0 收藏0
LeetCode 331. Verify Preorder Serialization of a B

摘要：如果它是一个空节点，我们可以使用一个标记值记录，例如。例如，上面的二叉树可以被序列化为字符串，其中代表一个空节点。每个以逗号分隔的字符或为一个整数或为一个表示指针的。如果满足前序遍历，那么最后栈中有且仅有一个元素，且是。 Description One way to serialize a binary tree is to use pre-order traversal. When ...

张巨伟 2019-07-31 10:10 评论0 收藏0
Verify Preorder Serialization of a Binary Tree

摘要：令，那么从累加会一直保持正，最后为。从左往右比较好理解，因为总是总到左再到右，的总是的，所以一定是保持。注意从开始，因为没有。 Verify Preorder Serialization of a Binary Tree 题目链接：https://leetcode.com/problems... recursion，用个全局的index： public class Solution {...

melody_lql 2019-08-14 17:23 评论0 收藏0
leetcode449. Serialize and Deserialize BST

摘要：题目要求将二叉搜索树序列化和反序列化，序列化是指将树用字符串的形式表示，反序列化是指将字符串形式的树还原成原来的样子。假如二叉搜索树的节点较多，该算法将会占用大量的额外空间。题目要求 Serialization is the process of converting a data structure or object into a sequence of bits so that...

Honwhy 2019-08-16 16:58 评论0 收藏0
[LeetCode] 109. Convert Sorted List to Binary Sear

Problem Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in whi...

dongfangyiyu 2019-08-16 13:42 评论0 收藏0