计算二叉树的单个垂直行中的节点之和

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

             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.One 的集合数据类型 方法二是 2 个数组，其中一个用于 存储负索引（映射到 积极）和一个积极的 索引（根的右侧）。但是我们 不知道数组的大小是多少 将。
3. 一种方法是使用双链接 列表并在右/左添加节点 如有必要，请移动。不是 得到我该如何实现这个 方法？任何其他简单/更多时间 有效的方法？
4. 上面代码的复杂度是 我的时间复杂度是 O(n)？ （我不擅长 分析时间复杂度，所以 问）

C++ code

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

EDIT:

澄清需求后，这里是建议的代码。请注意，这是 C++ 风格的，并不完全使用 Java 或 C++ 的列表标准 API，但您应该明白这个想法。我假设addNodeBefore and 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;
}