各ノードのBST内の最長パス

Question

BST内の各ノードについて、ノードからリーフまでの最長パスの長さはどのくらいですか？ （最悪の場合） 最悪の場合、ノードからリーフまでの線形パスがあると思います。ツリー内にn個のノードがある場合、実行時間はO（n * n）です。これは正しいですか？

Answer 1

これは、「すべてのリーフに与えられたノード」または「与えられたリーフに対してすべてのノード」と仮定すると、線形時間で実行できます。それが「すべてのノードからすべてのリーフ」の場合、それは少し難しくなります。

これを行うには：「ターゲット」からルートに移動し、各ノードに距離をマークします。これらのノードのすべてを赤色に着色します。 （したがって、ルートはターゲットの深さを保持し、ターゲットは0を保持します）。赤いノードごとに、赤いノードの値から始めて、降りるにつれて1を加えて、赤ではない子を歩きます。

多くの作業を再利用できるため、O（n * n）ではありません。あなたは1つのパスを見つけられず、次に完全に始まり、次のパスを見つける。

Answer 2

葉のノードから最長パスは、ノードから確実にするために最も深い葉
3.Thingsまでのルートから行くルート
2.Thenへのすべての道を行く
1.だろうこれ許可された場合、パスは任意の2つのノード間を移動して、無限に長くすることができたので、二回のノードを通過しないだろう、複数回

x 
/\ 
    b a 
     \ 
     c 
     \ 
      d 

Cから葉までの最長のパスは2つのこと
1を行うだろう.cからxまで（この長さを数える）
2. xからその経路にcを持たない最も深い葉に移動する（この場合、葉はbである）

以下のコードは、1つのノードから最長の距離を求めるためにO（n） したがってすべてのノードの距離を求めるO（N^2）私の解決策は次のようになり

public int longestPath(Node n, Node root) { 
    int path = 0; 
    Node x = n; 
    while (x.parent != null) { 
     x = x.parent; 
     path++; 
    } 
    int height = maxHeight(root, n); 
    return path + height; 
} 

private int maxHeight(Node x, Node exclude) { 
    if (x == exclude) 
     return -1; 
    if (x == null) 
     return -1; 
    if (x.left == null && x.right == null) 
     return 0; 
    int l = maxHeight(x.left, exclude); 
    int r = maxHeight(x.right, exclude); 
    return l > r ? l + 1 : r + 1; 
} 

Answer 3

あろう。

1）ノードにサブツリーがあるかどうかを確認し、そうであればそのサブツリーの高さを見つけます。

2）theresのように、2つの高さ