Leetcode: 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?
4
/ \
2 6
/ \ / \
1 3 5 7
如图所示BST, preorder结果是 4 2 1 3 6 5 7
4是root, 213是左子树,657是右子树
idea就是右子树不能再出现比root小的数,一旦出现,return false. 这样一层一层recursion, 直到子树只剩一个node, return true
1 public class Solution { 2 public boolean verifyPreorder(int[] preorder) { 3 if(preorder==null || preorder.length==0) return true; 4 return helper(0, preorder.length-1, preorder); 5 } 6 7 public boolean helper(int l, int r, int[] preorder) { 8 if (l >= r) return true; 9 int root = l; 10 int right = l-1; 11 boolean found = false; 12 for (int i=l+1; i<=r; i++) { 13 if (preorder[i] > preorder[root]) { //found right subtree 1st node 14 if (!found) { 15 found = true; 16 right = i; 17 } 18 } 19 else { 20 if (found) return false; 21 } 22 } 23 if (!found) return helper(root+1, r, preorder); 24 else return helper(root+1, right-1, preorder) && helper(right, r, preorder); 25 } 26 }
这样时间代价很大
更好的方法,参考https://leetcode.com/discuss/51543/java-o-n-and-o-1-extra-space
Time: O(N), Space: O(H)
imulate the traversal, keeping a stack of nodes. If the next number is smaller than the last stack value, then we're still in the left subtree of all stack nodes, so just push the new one onto the stack. Otherwise, pop all smaller ancestor values, as we must now be in their right subtrees (or even further, in the right subtree of an ancestor). Also, use the popped values as a lower bound, since being in their right subtree means we must never come across a smaller number anymore.
1 public boolean verifyPreorder(int[] preorder) { 2 int low = Integer.MIN_VALUE; 3 Stack<Integer> path = new Stack(); 4 for (int p : preorder) { 5 if (p < low) 6 return false; 7 while (!path.empty() && p > path.peek()) 8 low = path.pop(); 9 path.push(p); 10 } 11 return true; 12 }
Solution 2 ... O(1) extra space
Same as above, but use the given array as the stack. i refer to the stack.top.next
1 public boolean verifyPreorder(int[] preorder) { 2 int low = Integer.MIN_VALUE, i = 0; 3 for (int p : preorder) { 4 if (p < low) 5 return false; 6 while (i > 0 && p > preorder[i-1]) 7 low = preorder[--i]; 8 preorder[i++] = p; 9 } 10 return true; 11 }
i refer to stack.top
1 public boolean verifyPreorder(int[] preorder) { 2 int low = Integer.MIN_VALUE, i = -1; 3 for (int p : preorder) { 4 if (p < low) 5 return false; 6 while (i >= 0 && p > preorder[i]) 7 low = preorder[i--]; 8 preorder[++i] = p; 9 } 10 return true; 11 }
相关文章
- Leetcode: Closest Leaf in a Binary Tree
- Leetcode: Graph Valid Tree && Summary: Detect cycle in undirected graph
- Summary: Lowest Common Ancestor in a Binary Tree & Shortest Path In a Binary Tree
- Find Minimum in Rotated Sorted Array -- LeetCode
- LeetCode Kth Smallest Element in a BST
- 【LeetCode-面试算法经典-Java实现】【033-Search in Rotated Sorted Array(在旋转数组中搜索)】
- JS leetcode 有多少小于当前数字的数字 解题分析,你应该了解的桶排序
- JS leetcode 最大连续1的个数 题解分析
- ChatGPT教程之 04 使用 ChatGPT 解决 Leetcode 难题?
- [LeetCode]1431. 拥有最多糖果的孩子
- 【LeetCode】187. Repeated DNA Sequences
- LeetCode——Median of Two Sorted Arrays
- [LeetCode] 1269. Number of Ways to Stay in the Same Place After Some Steps 停在原地的方案数
- [LeetCode] 1192. Critical Connections in a Network 查找集群内的关键连接
- [LeetCode] 1163. Last Substring in Lexicographical Order 按字典序排在最后的子串
- [LeetCode] 1039. Minimum Score Triangulation of Polygon 多边形三角形化的最小得分
- [LeetCode] 979. Distribute Coins in Binary Tree 在二叉树中分配硬币
- [LeetCode] 937. Reorder Data in Log Files 日志文件的重新排序
- [LeetCode] 834. Sum of Distances in Tree 树中距离之和
- [LeetCode] Find Largest Value in Each Tree Row 找树每行最大的结点值
- [LeetCode] K-th Smallest in Lexicographical Order 字典顺序的第K小数字
- [LeetCode] Additive Number 加法数
- [LeetCode] Reverse Words in a String 翻转字符串中的单词
- [LeetCode] 26. Remove Duplicates from Sorted Array 有序数组中去除重复项
- [LeetCode] 153. Find Minimum in Rotated Sorted Array 寻找旋转有序数组的最小值