计算二叉树的单个垂直线中的节点总和

Question

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

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

如果你看上面的 T 恤

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 集合数据类型的情况下做到这一点。一种方法是两个是 2 个数组，一个用于存储负索引（映射到正），一个用于存储正索引（根的右侧）。但是我们不知道数组的大小是多少。
3. 一种方法是使用双链表，并在必要时添加一个向右/向左移动的节点。不明白我该如何实施这种方法？任何其他简单/更省时的方法？
4. 我imolmeted的上述代码的复杂度是O(n)吗？（我不擅长分析时间复杂度，所以问）

Answer 1

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;
}