5

对于二叉树，我想获得落在单个垂直线上的所有节点的总和。我想要每个verticle节点中的节点总和

             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. 一种方法是使用双向链表并在必要时在右/左移动时添加一个节点。我没有得到如何实施这种方法？还有其他简单/更省时的方法吗？
  4. 我imolmeted的上述代码的复杂度是O（n）吗？（不擅长分析时间复杂度，所以问）
4

4 回答 4

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)，即我们总是从节点A（根的树）开始访问，它位于第 0 列，我们的目标是第 -1 列。我们得到以下信息：

树列调用

因此visit(A, 0, -1) = B + I + N正如预期的那样。

复杂度总是 O(n)，其中 n 是树中的节点数，因为我们以深度优先后序访问整个树，并且我们只处理每个节点一次。

如果我们想计算每一列的总和，我们可以使用下面的算法

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

并调用一次visit(A, 0)，A根节点在哪里。请注意，S{...}在算法中是一个映射，其键是列号 (..., -2, -1, 0, 1, 2, ...)，其值（在算法结束时）是该列中节点的值（S{1}将是第 1 列中节点的总和）。如果我们注意索引（数组没有负索引），我们也可以使用数组而不是映射。该算法仍然是 O(n)，因为我们只遍历整个树一次。但是，在这种情况下，我们需要额外的空间来存储所有列（映射或数组）的总和。如果我没记错的话，高度的二叉树h将有2*h + 1列。

于 2011-05-11T08:32:39.957 回答
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并addNodeAfter初始化节点的数据（即ListNode::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 回答
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 回答
0 
public class Solution {

    public static int getSum(BinaryTreeNode<Integer> root) {
        //Your code goes here.
        if(root==null){
            return 0;
        }
       int leftnodesum=getSum(root.left);
       int rightnodesum=getSum(root.right);

    
    return root.data+leftnodesum+rightnodesum;
    }
}
于 2021-07-20T19:51:19.393 回答