範囲に含まれるbstの最大サブツリーのサイズを調べる

Question

これは最近のインタビューの質問でした。その質問は、範囲[x, y]に含まれるBSTの最大サブツリーのサイズがx < yであることを確認するよう求められました。 BSTは、各ノードが整数値、左の子ノード、および右の子ノードを有する場合に再帰的に定義される。私はその範囲内にあるが最大のサブツリーを見つけることができなかったツリー内のノードの総数にしかできませんでした。ここで私が使用したコードはPythonで、です：

def solution(x, y, T): 
    if T is None: 
     return 0 
    size = 0 
    if x < T.val: 
     size += solution(x, y, T.left) 
    if x <= T.val and y >= T.val: 
     size += 1 
    # The following if statement was my attempt at resetting the count 
    # whenever we find a node outside the range, but it doesn't work 
    if x > T.val or y < T.val: 
     size = 0 
    if B > T.x: 
     size += solution(A, B, T.right) 
    return size 

Nは、ツリー内のノードの数であるソリューションはO(N)する必要があります。 BST内の各ノードで

Answer 1

、それが有効な範囲内で、そのノードの嘘のサブツリー内のすべての要素ことを意味する、[Li,Ri]を言うためには、有効な範囲を関連付けることができます。

あなたは簡単に再帰的にこれらの範囲を定義することができます

ノードiについての範囲は[Li, Ri]であり、このノードに格納された値がvalあるとしましょう。 iの左の子の場合、範囲は[Li, val − 1]です。そして同様に右の子供のための範囲は[val + 1, Ri]です。

ルートノードの有効範囲は[−inf, inf]です。

Answer 2

私たちは再帰的に問題を解決することができます。各サブツリーの左と右の境界（つまり、最小要素と最大要素）を知る必要があります。範囲[x、y]にある場合、現在のサブツリーの合計サイズで答えを更新することができます。ここにいくつかのコードがあります（solution関数は答えの上にいくつかの余分な情報を含むタプルを返します。範囲内の最大のサブツリーのサイズを返すだけなら、それを包み込んでヘルパー関数として使用できます）。

このソリューションは、すべてのノードを1回だけ訪れ、ノードごとに一定数の操作を実行するため、明らかに線形時間で実行されます。

Answer 3

無効なサブツリーに対して-1が返されたとします。ノードの値とそのサブツリー内のすべての値の両方が範囲内にある場合、（サブ）ツリーは有効です。

# returns a tuple: (size of T, best valid size among itself and its subtrees) 
def f(x,y,T): 
    if T is None: 
    return (0,0) 

    l_size, l_best = f(x,y,T.left) 
    r_size, r_best = f(x,y,T.right) 

    if x <= T.value <= y and l_size >= 0 and r_size >= 0: 
    return (1 + l_size + r_size,1 + l_size + r_size) 
    else: 
    return (-1,max(l_best,r_best))