、DFSとBFSを別々に研究しました。この節では、特殊なバイナリ木構造である バイナリ探索木を引き続き研究します。
バイナリサーチ・ツリー
左の部分木が空でない場合、左の部分木のすべてのノードの値は、そのルートノードの値よりも小さいです。右の部分木が空でない場合、右の部分木のすべてのノードの値は、そのルートノードの値よりも大きいです。
ここでサブツリーという概念を強調します：Tを根付き木、aをTの頂点とします。 **aとa **のすべての子孫から派生する部分グラフを有向木Tのサブツリーと呼びます。具体的には、サブツリーとは、有向木のノードの1つと、それ以下のすべてのノードから構成される木のことです。
例えば、以下はバイナリー・サーチツリーです：
以下のどちらでもありません：
<1>グラフの4ノードの位置の値は、ルートノードより大きくなければなりません。
<2>グラフの3ノードの位置の値は、ルートノードより大きくなければなりません。
バイナリ探索木の検証方法を教えてください。質問を見てください。
トピックは以下の本で分析されています。
| 2進木が与えられたとき、それが有効な2進探索木かどうかを判定します。 |
例1.
:
5
/ \
1 4
/ \
3 6
: false
: : [5,1,4,null,null,3,6]
ルート・ノードの値は5だが、その右の子の値は4である。
例2.
:
5
/ \
1 4
/ \
3 6
: false
: : [5,1,4,null,null,3,6]
ルート・ノードの値は5だが、その右の子の値は4である。
<节点值，右节点值＞节点值>まず、設問を読んだ後、木全体を走査し、すべてのノードを比較し、左のノードの値を渡すことを思い浮かべるのは簡単です。そこでここでは、ノードに発生する最大値と最小値を保持するために、上界と下界を導入します。
再帰的な解法
トピックが明確になれば、再帰を使った解法は簡単です。ここで強調しておきたいのは、各再帰において、左ノードと右ノードのチェックサムに加え、上界と下界の判定も必要だということです。この再帰は解析が難しいので、最初にコードを示します：
func isValidBST(root *TreeNode) bool {
if root == nil{
return true
}
return isBST(root,math.MinInt64,math.MaxInt64)
}
func isBST(root *TreeNode,min, max int) bool{
if root == nil{
return true
}
if min >= root.Val || max <= root.Val{
return false
}
return isBST(root.Left,min,root.Val) && isBST(root.Right,root.Val,max)
}
走行結果
もし上記の記事の再帰があまりにわかりにくければ、以下の図で理解することができます：
私が書いたすべての解答と各問題の完全な図解をeBookにまとめました。
