5

二分木の場合、1 つの垂直線に含まれるすべてのノードの合計を取得したいと考えています。各頂点ノードのノードの合計が必要です

             A
           /    \
          B      C
         /  \   /  \
         D   E  F   G
        / \ 
        H  I

ティーの上を見ると

line 0   A  E F   so sum  = A+E+F
line -1  B I      so sum = B +I
line 1   C        so sum = C
line 2   G        so sum = G

次のアルゴリズムを実装しました

Map<Integer,Integere> mp = new HashMap<Integer,Integer>()
calculate(root,0); 

 void calculate(Node node, int pos){
   if(node==null)
        return ;
  if(mp.containsKey(pos) ){
    int val = mp.get(pos) + node.data;
     mp.put(pos,val);
    }
    else{ 
         mp.put(pos,node.data);
    }

    calculate(node.left,pos-1);
    calculate(node.right,pos+1);

}
  1. 上記のアルゴリズムは問題ないと思います。確認できる人はいますか?
  2. また、HashMap、arraylist、またはJavaのそのようなコレクションデータ型を使用せずにそれを行うにはどうすればよいですか。配列のサイズがどうなるかわかりません。
  3. 1 つのアプローチは、二重リンク リストを使用し、必要に応じて左右の移動にノードを追加することです。このアプローチをどのように実装できますか? 他の単純な/より時間効率の良いアプローチはありますか?
  4. 上記のコードの複雑さは O(n) ですか? （時間の複雑さを分析するのが苦手なので、質問します）
4

4 に答える 4

2

C++ コード

int vertsum(Node* n, int cur_level, int target_level)
{
  if (!n)
    return 0;

  int sum = 0;
  if (cur_level == target_level)
    sum = n->value;
  return sum + 
         vertsum(n->left, cur_level-1, target_level) + 
         vertsum(n->right, cur_level+1, target_level);
}

呼び出し例:

vertsum(root, 0, 1);

編集：

要件を明確にした後、ここで提案されたコード。これは C++ 風であり、Java または C++ のリスト用の標準 API を正確に使用しているわけではありませんが、アイデアは理解できるはずです。私はそれを仮定し、ノードのデータaddNodeBeforeを初期化します（つまり）addNodeAfterListNode::counter

void vertsum(TreeNode* n, int level, ListNode& counter)
{
  if (!n)
    return;

  counter.value += n->value;
  counter.index = level;

  if (! counter.prev)
    addNodeBefore(counter);
  vertsum(n->left, level-1, counter.prev);             

  if (! counter.next)
    addNodeAfter(counter);
  vertsum(n->right, level+1, counter.next);

  return;
}
于 2011-05-11T09:35:55.510 に答える
2

二分木に深さ優先の後順でアクセスし、オフセットを使用して、開始ノードに対して左/右にどれだけ移動したかを追跡できます。左に移動するたびにオフセットが減少し、右に移動するたびにオフセットが増加します。訪問手順が のオフセットで呼び出された場合、訪問0されているノードが開始ノードと同じオフセットを持っている (つまり、同じ列にある) ことを意味するため、その値を追加する必要があります。

擬似コード:

procedure visit (node n, int offset) {
  sumleft = 0
  sumright = 0
  if (n.left != null)
    sumleft = visit(n.left, offset - 1)
  if (n.right != null)
    sumright = visit(n.right, offset + 1)
  if (offset == 0)
    return n.value + sumleft + sumright
  else
    return sumleft + sumright;
}

たとえば、

visit(A, 0)

次の呼び出しが表示されます。

visit(A, 0) -> E.value + F.value + A.value
  visit(B, -1) -> E.value
    visit(D, -2) -> 0
      visit(H, -3) -> 0
      visit(I, +2) -> 0
    visit(E, 0) -> E.value
  visit(C, +1) -> F.value
    visit(F, 0) -> F.value
    visit(G, +1) -> 0

node から始まる別の例B:

visit(B, 0)
  visit(D, -1) 
    visit(H, -2)
    visit(I, 0) -> here we return I.value
  visit(E, +1)

再帰が と の最初の呼び出しvisit(B, 0)に戻るsumleft = I.valueとsumright = 0、期待どおり最終的な結果が返さB.value + I.valueれます。

開始ノードをルートとするツリーのすべてのノードに一度アクセスするため、O(n) の複雑さ。

上記のアルゴリズムについて考えた後、次のようなより複雑なツリーを検討すると明らかになる制限があることに気付きました。

木の柱

この場合visit(B, 0)でも が返されますが、 も同じ列にあるB.value + I.valueため、これは期待される結果ではありません。N次のアルゴリズムは、この問題に対処する必要があります。

procedure visit(node n, int c, int t) {
  sumleft = 0;
  sumright = 0;
  if (n.left != null)
    sumleft = visit(n.left, c - 1, t)
  if (n.right != null)
    sumright = visit(n.right, c + 1, t)
  if (c == t)
    return n.value + sumleft + sumright;
  else
    return sumleft + sumright;
}

考え方は基本的に同じですがc、現在の列を指定するパラメーターtと、ターゲット列を指定するパラメーターがあります。列の要素の合計が必要な場合は、Bを呼び出すことができますvisit(A, 0, -1)。つまり、常に列 0 にあるノード (ルートのツリー) から訪問を開始しA、ターゲットは列 -1 です。次の結果が得られます。

ツリー列の呼び出し

したがってvisit(A, 0, -1) = B + I + N、予想どおり。

複雑さは常に O(n) です。n はツリー内のノードの数です。深さ優先の後順でツリー全体を調べ、各ノードを 1 回だけ処理するためです。

すべての列の合計を計算したい場合は、次のアルゴリズムを使用できます

procedure visit(node n, int c) {
  if (n.left != null)
    S{c} += n.value;
    visit(n.left, c - 1)
    visit(n.right, c + 1)
}

と呼び出し once visit(A, 0)、ここAで はルートノードです。S{...}アルゴリズムには、キーが列番号 (...、-2、-1、0、1、2、...) であり、値 (アルゴリズムの最後) が合計であるマップがあることに注意してください。その列のノードの値 (S{1}は列 1 のノードの合計になります)。インデックスに注意を払えば、マップの代わりに配列を使用することもできます (配列には負のインデックスがありません)。ツリー全体を 1 回だけトラバースするため、アルゴリズムは O(n) のままです。ただし、この場合、すべての列 (マップまたは配列) の合計を格納するために追加のスペースが必要です。私が間違っていなければ、高さの二分木にhは2*h + 1列があります。

于 2011-05-11T08:32:39.957 に答える
0

以下はどうですか？(ノード クラス内で、getData が整数値を返すと仮定すると、hasRight() と hasLeft() は右/左ブランチが存在するかどうかを示すブール値であり、getRight() と getLeft() は右/左ブランチの次のノードを返します。

public int calculateVerticalLine(int numLine) {
    return calculateVerticalLineRecursive(numLine, 0);
}

protected int calculateVerticalLineRecursive(int numLine, int curPosition) {
    int result = 0;
    if(numLine == curPosition) result += this.getData();
    if(hasRight()) result += getRight().calculateVerticalLineRecursive(numLine, curPosition+1);
    if(hasLeft()) result += getLeft().calculateVerticalLineRecursive(numLine, curPosition-1);
    return result;
}
于 2011-05-11T07:06:38.967 に答える