traversal - 指定された注文が合法的なポストオーダー トラバーサルかどうかを確認する

Question

整数 0 から 9 を格納する 10 個のノードを持つ二分探索木がある場合、シーケンスが木の後順トラバーサルを表現できないかどうかをどのように判断しますか? ルートはシーケンスの最後でなければならないことは理解していますが、どのパターンにも到達できませんでした。疑似コードも素晴らしいでしょう！（宿題ではありません、面接の練習です）

Answer 1

あなたが言ったように、あなたは根が何であるかを知っています。したがって、各サブツリーの値の範囲がわかります。ルートを差し引いたシーケンスが、ルートよりも小さいシーケンスと大きいシーケンスの 2 つのシーケンスに分割されない場合、それは有効ではありません。存在する場合は、2 つのサブトラバーサルを再帰的にチェックする必要があります。すべてが機能する場合、それは有効です。