☰

二分木が二分探索木であるかどうかを調べる [重複] 質問する

tag-icon • tag-icon algorithm binary-tree binary-search-tree
二分木が二分探索木であるかどうかを調べる [重複] 質問する

今日、面接があり、バイナリ ツリーを受け取り、それがバイナリ検索ツリーでもある場合は true を返し、そうでない場合は false を返すプログラムを作成するように求められました。

私のアプローチ 1: 順序どおりにトラバーサルを実行し、要素を O(n) 時間で格納します。次に、要素の配列/リストをスキャンし、i 番目のインデックスの要素が (i+1) 番目のインデックスの要素より大きいかどうかを確認します。このような条件に遭遇した場合は、false を返してループを終了します (これには O(n) 時間がかかります)。最後に true を返します。

しかし、この紳士は私に効率的な解決策を提供してほしいと言っていました。私は試みましたが、BST かどうかを確認するには各ノードをチェックする必要があるため、失敗しました。

さらに、彼は私に再帰について考えるように指示していました。私のアプローチ 2: 任意のノード N について、N->left が < N かつ N->right > N であり、N の左ノードの順序どおりの後続ノードが N より小さく、N の右ノードの順序どおりの後続ノードが N より大きく、左と右のサブツリーが BST である場合、BT は BST です。

しかし、これは複雑になり、実行時間も良くないようです。最適な解決策をご存知でしたら、ご協力ください。

ベストアンサー1

これはかなりよく知られた問題で、答えは次のようになります。

public boolean isValid(Node root) {
     return isValidBST(root, Integer.MIN_VALUE,
          Integer.MAX_VALUE);
}
private boolean isValidBST(Node node, int l, int h) {
     if(node == null)
         return true;
     return node.value > l 
         && node.value < h
         && isValidBST(node.left, l, node.value)
         && isValidBST(node.right, node.value, h);
}

再帰呼び出しにより、サブツリー ノードがその祖先の範囲内にあることが保証されます。これは重要です。すべてのノードが 1 回検査されるため、実行時間の複雑さは O(n) になります。

もう 1 つの解決策は、特にバイナリ ツリーが入力として提供されていることが既にわかっている場合は、inorder トラバーサルを実行してシーケンスがソートされているかどうかを確認することです。

おすすめ記事