/*
* 255. Verify Preorder Sequence in Binary Search Tree
Total Accepted: 8634 Total Submissions: 23097 Difficulty: Medium
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?
Hide Company Tags Zenefits
Hide Tags Tree Stack
Hide Similar Problems (M) Binary Tree Preorder Traversal
*/
package tree;
import java.util.Stack;
public class VerifyPreOrderBST {
public boolean verifyPreorder(int[] preorder) {
// store the nodes using a stack path. if path.isEmpty() or p < path.peek(), we still in the left subtree, just push p into path; if p > path.peek(), we pop the node as a low bound, push p into path. For the next p if smaller than low bound. return false, since being in their right subtree means we must never come across a smaller number anymore.
// https://leetcode.com/discuss/51543/java-o-n-and-o-1-extra-space
// test case : [4, 2, 1, 3, 6, 8,5] => false
if (preorder == null || preorder.length == 0) {
return true;
}
int low = Integer.MIN_VALUE;
Stack<Integer> path = new Stack<>();
for (int p : preorder) {
if (p < low) {
return false;
}
while (!path.isEmpty() && p > path.peek()) {
low = path.pop();
}
path.push(p);
}
return true;
}
}
255. Verify Preorder Sequence in Binary Search Tre
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門吓揪，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人所计，你說我怎么就攤上這事柠辞。” “怎么了主胧？”我有些...
- 文/不壞的土叔 我叫張陵叭首，是天一觀的道長。 經(jīng)常有香客問我踪栋，道長焙格，這世上最難降的妖魔是什么？ 我笑而不...
- 正文 為了忘掉前任夷都，我火速辦了婚禮眷唉，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘囤官。我一直安慰自己冬阳，他們只是感情好，可當(dāng)我...
- 文/花漫 我一把揭開白布党饮。 她就那樣靜靜地躺著肝陪，像睡著了一般。 火紅的嫁衣襯著肌膚如雪刑顺。 梳的紋絲不亂的頭發(fā)上氯窍，一...
- 文/蒼蘭香墨 我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼鲫骗！你這毒婦竟也來了犬耻？” 一聲冷哼從身側(cè)響起，我...
- 正文 年R本政府宣布毯侦，位于F島的核電站，受9級特大地震影響具垫，放射性物質(zhì)發(fā)生泄漏侈离。R本人自食惡果不足惜，卻給世界環(huán)境...
- 文/蒙蒙 一筝蚕、第九天 我趴在偏房一處隱蔽的房頂上張望卦碾。 院中可真熱鬧，春花似錦饰及、人聲如沸蔗坯。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽宾濒。三九已至，卻和暖如春屏箍，著一層夾襖步出監(jiān)牢的瞬間绘梦，已是汗流浹背橘忱。 一陣腳步聲響...
推薦閱讀更多精彩內(nèi)容
- Given an array of numbers, verify whether it is the corre...
- Given an array of numbers, verify whether it is the corre...
- 解題思路 ： recursive 作業(yè)順序： 往左檢查 left child 只要有符合 > k1 的 node ...
- Search Range in Binary Search Tree 今天是一道有關(guān)二叉樹的題目疹鳄，來自LintCo...
- 項目人力資源管理包括組織拧略、管理與領(lǐng)導(dǎo)團(tuán)隊的各個過程。 讓項目團(tuán)隊成員全員參與項目規(guī)劃和決策仍是有益的瘪弓，增強責(zé)任感垫蛆。...
