255.Verify Preorder Sequence in Binary Search Tree
发布时间:2020-12-14 04:15:42 所属栏目:大数据 来源:网络整理
导读: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.Consider the following?binary search tree:? 5 / 2 6 / 1 3 Example 1 :Input:
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. Consider the following?binary search tree:? 5 / 2 6 / 1 3 Example 1: Input: [5,2,6,1,3] Output: false Example 2: Input: [5,3,6] Output: true Follow up:?Could you do it using only constant space complexity? Solution 1 Kinda simulate the traversal,keeping a stack of nodes (just their values) of which we‘re still in the left subtree. 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. But before that,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. public boolean verifyPreorder(int[] preorder) { int low = Integer.MIN_VALUE; Stack<Integer> path = new Stack(); for (int p : preorder) { if (p < low) return false; while (!path.empty() && p > path.peek()) low = path.pop(); path.push(p); } return true; } Solution 2?...?O(1) extra space Same as above,but abusing the given array for the stack. public boolean verifyPreorder(int[] preorder) { int low = Integer.MIN_VALUE,i = -1; for (int p : preorder) { if (p < low) return false; while (i >= 0 && p > preorder[i]) low = preorder[i--]; preorder[++i] = p; } return true; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |