バイナリ検索ツリーの検証: インターネット上の古典的なアルゴリズム

[[427951]]

この記事はWeChatの公開アカウント「Programmer Bear」から転載したもので、著者はDineです。この記事を転載する場合は、プログラマーXiaoxiongの公式アカウントまでご連絡ください。

序文

みなさんこんにちは。私はHuaweiのプログラマー、Xiao Xiongです。今日は、バイナリツリーに関連する高頻度の面接の質問を紹介します。この質問は、過去6か月間にGoogle、ByteDance、Microsoft、Amazonなどの大手企業で面接の質問として使用されました。それは、Likouの質問98 - バイナリ検索ツリーの検証です。

この記事では、主にこの問題を解決するための再帰と深さ優先探索の 2 つの方法を紹介します。参考になれば幸いです。

二分探索木の検証

バイナリツリーのルートが与えられた場合、それが有効なバイナリ検索ツリーであるかどうかを判断します。

有効な二分探索木は次のように定義されます。

ノードの左のサブツリーには、現在のノードより小さい数値のみが含まれます。

ノードの右サブツリーには、現在のノードより大きい数値のみが含まれます。

すべての左および右のサブツリー自体もバイナリ検索ツリーである必要があります。

例1

例2とヒント

二分探索木

タイトルは、有効な二分探索木の定義が次のようになることを示唆しています。

ノードの左のサブツリーには、現在のノードより小さい数値のみが含まれます。
ノードの右サブツリーには、現在のノードより大きい数値のみが含まれます。
すべての左および右のサブツリー自体もバイナリ検索ツリーである必要があります。

例

例1

例2

例3

二分探索木の判定

上記の例の場合、二分探索木の判定方法によれば、上記の例が二分探索木であるかどうかは以下のように判定されます。

例 1 は二分探索木ではありません。理由: ルートノード (値 6) の左サブツリー内のノード数 (値 7) がルートノードの数より大きくなっています。
例 2 は二分探索木ではありません。理由: ルートノード (値 6) の右サブツリー内のノード数 (値 3) がルートノードの数より少なくなっています。
例 3 は二分探索木ではありません。理由: ルートノードの左サブツリーは二分探索木ではありません。左サブツリーのルートノードの値 5 は、左子ノードの値 7 よりも小さいだけでなく、右子ノードの値 4 よりも大きくなっています。さらに、ルートノードの値 6 は、左サブツリーのノードの値 7 よりも小さくなっています。ルートノードの右サブツリーも二分探索木ではありません。右サブツリーのルートノードの値 8 は、右子ノードの値 3 よりも大きいだけでなく、左子ノードの値 9 よりも小さくなっています。さらに、ルートノードの値 6 は、右サブツリーのノードの値 3 よりも大きくなっています。

問題解決

二分探索木の定義によれば、木が二分探索木であるかどうかを判断するには、各ノードが二分木の特性を満たしているかどうかを判断する必要があり、判断の根拠は同じであるため、再帰的な方法を使用してこの問題を解決できます。

再帰

上記の判断の根拠（現在のノードに左と右の子ノードがあると仮定）は次のとおりです。

現在のノードの値が、その左の子の値よりも大きい。
現在のノードの値が、その右の子ノードの値よりも小さい。
現在のノードに左サブツリーと右サブツリーがある場合、その左サブツリーと右サブツリーのノードも次の条件を満たす必要があります。左サブツリーのノード値は現在のノードの値より小さく、右サブツリーのノード値は現在のノードの値より大きい。

上記の考え方に基づいて、上限と下限を設定することで、ノードがバイナリ検索ツリーの特性を満たしているかどうかを判断できます。

上限と下限がある場合は、ノードが境界内にあるかどうかを判断します。境界内にない場合は、バイナリ検索ツリーではありません。境界内にない場合は、ノードの値を上限として使用し、左のサブツリーを再帰的に決定します。ノードの値を下限として使用し、右のサブツリーを再帰的に決定します。

知らせ

空の木は二分探索木です。

コードを見せてください

Ｃ

 bool isValidBST_Helper(構造体 TreeNode* ルート、 double  最小、倍 最大）{
    /* 特別判定 */
    ルート == NULLの場合{
戻る 真実;
    } 
 
    /* 現在のノードは上限と下限の範囲内にありません。バイナリ検索ツリーではありません */
    ルート->val <=最小|| ルート->val >=最大) {
戻る 間違い;
    } 
 
    /* 左と右のサブツリーが二分探索木であるかどうかを判定する */
 isValidBST_Helper(root-> left , min , root->val) && isValidBST_Helper(root-> right , root->val, max )を返します。
 } 
 
 bool isValidBST(構造体TreeNode*ルート) {
 isValidBST_Helper(root, LONG_MIN, LONG_MAX) を返します。
 }

C++

 bool isValidBST_Helper(TreeNode* ルート、 double  最小、倍 最大）{
    ルート == nullptr の場合 {
戻る 真実;
    } 
 
    （ルート->val <=最小|| ルート->val >=最大）{
戻る 間違い;
    } 
 
 isValidBST_Helper(root-> left , min , root->val) && isValidBST_Helper(root-> right , root->val, max )を返します。
 } 
 
ブール isValidBST(TreeNode* ルート) {
 isValidBST_Helper(root, LONG_MIN, LONG_MAX) を返します。
 }

ジャワ

ブール値 isValidBST_Helper(TreeNode ルート、 double  最小、倍 最大）{
    ルートがnullの場合
戻る 真実;
    } 
 
    (root.val <= min || root.val >= max ) の場合 {
戻る 間違い;
    } 
 
 isValidBST_Helper(root.left , min , root.val) && isValidBST_Helper(root.right , root.val, max )を返します。
 } 
 
ブール値 isValidBST(TreeNode ルート) {
 isValidBST_Helper(ルート、Long.MIN_VALUE、Long.MAX_VALUE)を返します。
 }

Python3

 def isValidBST(self, ルート: TreeNode) -> bool:
    isValidBST_Helperを定義します(ルート、最小値、右):
        ルートがNoneの場合:
戻る 真実  
         
        root.val <= minの場合 またはroot.val >= right :
戻る 間違い  
 
 isValidBST_Helper(root.left , min , root.val)とisValidBST_Helper ( root.right , root.val, right )を返します。 
 
 isValidBST_Helper(root, - float ( 'inf' ), float ( 'inf' ))を返します

Go言語

func isValidBST(root *TreeNode) ブール値 {
 isValidBST_Helper(root, math.MinInt64, math.MaxInt64)を返します。
 } 
 
 func isValidBST_Helper(root *TreeNode,最小値,最大値 整数)ブール{
  ルート == nilの場合{
戻る 真実 
  } 
 
  min >= root.Val || max <= root.Val {の場合
戻る 間違い 
  } 
 
 isValidBST_Helper(root.Left , min , root.Val)を返します&& isValidBST_Helper ( root.Right , root.Val, max )
 }

複雑性分析

時間計算量: O(n)、ここで n はバイナリツリーノードの数です。

空間計算量: O(n)。

深さ優先探索

バイナリ検索木の特性によれば、バイナリ検索木に対して順序どおりのトラバーサルを実行すると、結果の配列は昇順になる必要があります。したがって、この特徴に基づいて、ツリーが二分探索ツリーであるかどうかを判断できます。

インオーダートラバーサルを使用する場合、バイナリツリーのすべてのノードの値を配列に格納し、配列が昇順になっているかどうかを判断します。手順は少し面倒です。

配列が昇順になっているかどうかを判断するには、配列の次の要素が前の要素より大きいかどうかを判断するだけで済みます。したがって、順序どおりにトラバーサルするときに前のノードの値を保存する変数を設定し、現在のノードの値が変数によって保存された値より大きいかどうかを判断できます。

大きくない場合は、ツリーがバイナリ検索ツリーではないことを意味します。それ以外の場合は、トラバースと判断を続けます。

コードを見せてください

C++

ロングプレ = LONG_MIN;
ブール isValidBST(TreeNode* ルート) {
    ルート == nullptr の場合 {
戻る 真実;
    } 
 
    if (!isValidBST(root-> left )) {
戻る 間違い;
    } 
 
    ルート>val <= preの場合{
戻る 間違い;
    } 
 
    pre = ルート->val;
 isValidBST(root-> right )を返します。
 }

ジャワ

長いtemp = Long.MIN_VALUE;
ブール値 isValidBST(TreeNode ルート) {
    ルートがnullの場合
戻る 真実;
    } 
 
    if(!isValidBST( root.left )) {
戻る 間違い;
    } 
 
    （root.val <= temp ）の場合{
戻る 間違い;
    } 
 
 temp = ルート.val;
 isValidBST ( root.right )を返します。
 }