计算二叉树的单个垂直线中节点的总和 [英] calculating the sum of nodes in a single verticle line of a binary tree

问题描述

对于一棵二叉树，我想获得落入一条垂直线的所有节点的总和.我想要每个顶点节点中的节点总数

For a binary tree i want to get the sum of all nodes that fall in a single verticle line. I want the sum of nodes in each verticle node

             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.One的集合数据类型 方法是两个是2个数组之一 存储负索引(映射到 积极)和一个积极 索引(根目录的右侧).但是我们 不知道数组的大小 会.
3. 一种方法是使用双向链接 列出并在右侧/左侧添加一个节点 必要时运动.不是 得到我该如何实施 方法?任何其他简单/更多的时间 有效的方法?
4. 是上面代码的复杂性 我不知是O(n)吗? (我不擅长 分析时间复杂度 问)

1. I think the above algo is fine.Can any one confirm?
2. Also how can i do it without using HashMap,arraylist or any such collection datatype of java.One method is two is 2 arrays one for storing negative indexes(mapped to positive) and one for positive indexs(right side of root).But we dont know what the size of array will be.
3. One approach is to use doubly link list and add a node on right/left movement if necessary. Am not getting how can i implement this approach? Any other simple/more time efficient approach?
4. Is the complexity of the above code i imolmeted is O(n)? (am not good at analysing time complexity , so asking )

推荐答案

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)

After clarifying the requirements, here the suggested code. Note that this is C++'ish and not exactly using Java's or C++'s standard API for lists, but you should get the idea. I assume that addNodeBefore and addNodeAfter initialize node's data (i.e. 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;
}

这篇关于计算二叉树的单个垂直线中节点的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！