面接問題33.二叉探索ツリーの後順ループシーケンス
整数配列を入力し、その配列が二叉探索ツリーの後順遍歴結果であるかどうかを判断します.もしそうであればtrueを返し、そうでなければfalseを返します.入力された配列の任意の2つの数字が互いに異なると仮定します.
次のツリーを参照してください.
5/2 6/1 3例1:
入力:[1,6,3,2,5]出力:false例2:
入力:[1,3,2,6,5]出力:true
コメントエリアの大物を参考にした単調なスタックは確かに巧妙だ
主な考え方は,二叉ソートツリーを利用してすべての右の木が左の木より数が大きいという考え方である.
次のツリーを参照してください.
5/2 6/1 3例1:
入力:[1,6,3,2,5]出力:false例2:
入力:[1,3,2,6,5]出力:true
コメントエリアの大物を参考にした単調なスタックは確かに巧妙だ
主な考え方は,二叉ソートツリーを利用してすべての右の木が左の木より数が大きいという考え方である.
bool verifyPostorder(vector& postorder) {
stack st;
int pre = INT_MAX;
// root -> right -> left right -> left
for(int i = postorder.size() - 1; i >= 0; i--){
if(postorder[i] > pre)return false;
//
while(!st.empty() && postorder[i] < st.top()){
pre = st.top();
st.pop();
}
st.push(postorder[i]);
}
return true;
}