摘要:如果继续降序,说明又向左走了,这样等到下次向右走得时候也要再次更新最小值。这样,序列无效的条件就是违反了这个最小值的限定。我们同样可以用本题的方法解,不过是从数组的后面向前面遍历,因为在后面了。栈的增长方向也是从高向低了。
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 12 / 2 6
如这个例子,我们在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 12 / 2 6
同样是看这个例子,我们序列是[10, 5, 2, 6, 12],如果用栈的话,遍历序列到第n个数时,栈中的情况是这样的:
1 | 10 2 | 10 5 3 | 10 5 2 4 | 10 6 5 | 12
可见我们栈的大小是不会超过我们当前遍历的数的位置的,所以我们大可以用该序列的之前遍历过的部分来当做我们的栈。这里用一个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; }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/64693.html
摘要:如果我们从右往左看先序遍历,就知道后两个节点如果遇到第三个节点,则该节点就应当是这两个节点的父节点。如果在遍历的过程中根节点数量小于,则说明这棵树有问题。而如果遍历结束之后,剩下的根节点数不等于,也说明这个先序遍历存在问题。 题目要求 One way to serialize a binary tree is to use pre-order traversal. When we en...
摘要:如果它是一个空节点,我们可以使用一个标记值记录,例如。例如,上面的二叉树可以被序列化为字符串,其中代表一个空节点。每个以逗号分隔的字符或为一个整数或为一个表示指针的。如果满足前序遍历,那么最后栈中有且仅有一个元素,且是。 Description One way to serialize a binary tree is to use pre-order traversal. When ...
摘要:令,那么从累加会一直保持正,最后为。从左往右比较好理解,因为总是总到左再到右,的总是的,所以一定是保持。注意从开始,因为没有。 Verify Preorder Serialization of a Binary Tree 题目链接:https://leetcode.com/problems... recursion,用个全局的index: public class Solution {...
摘要:题目要求将二叉搜索树序列化和反序列化,序列化是指将树用字符串的形式表示,反序列化是指将字符串形式的树还原成原来的样子。假如二叉搜索树的节点较多,该算法将会占用大量的额外空间。 题目要求 Serialization is the process of converting a data structure or object into a sequence of bits so that...
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...
阅读 522·2021-10-19 11:45
阅读 1321·2021-09-30 09:48
阅读 1450·2021-08-16 10:56
阅读 709·2021-07-26 23:38
阅读 3187·2019-08-30 13:15
阅读 2569·2019-08-30 12:45
阅读 1779·2019-08-29 12:14
阅读 1990·2019-08-26 18:42