给定二叉树中的垂直和

给定二叉树，找到垂直线上相同节点的垂直和。通过不同的垂直线打印所有的和。给定二叉树中的垂直和

要了解垂直线是什么，我们需要首先定义水平距离。如果两个节点具有相同的水平距离（HD），则它们位于相同的垂直线上。 HD的想法很简单。根的HD为0，右边缘（连接到右子树的边缘）被认为是+1水平距离，左边缘被认为是-1水平距离。例如，在上述树中，节点4的HD为-2，节点2的HD为-1，HD为5和6为0，节点7的HD为+2。

实例：

1 
/ \ 
2  3 
/\ /\ 
4 5 6 7

这棵树5条垂直线

垂直线-1只有一个节点4 =>垂直总和为4

垂直线-2：具有垂直线3：有三个节点：1,5,6 =>垂直和是1 + 5 + 6 = 12

垂直线-4：只有一个节点3 =>垂直总和是3

垂直线-5：仅具有一个节点7 =>垂直总和是7

所以预期的输出是4， 2，12，3,7

我的解决办法： 我想出来AO针对此问题（nlong（n））的溶液中。这个想法是：

（1）使用前序遍历为每个节点获取HD，并将HD及其关联节点存储在一个数组中。

（2）由HD对数组进行排序

（3）遍历所述排序后的数组打印结果。

我相信这不是最适合这个问题的。谁能帮助我提供更好的解决方案？

来源

2013-01-23 Fihop

为什么你存储每个节点？您只需存储每个HD的总和，并在遍历树时更新它。 –

[二叉树的垂直和]的可能重复（http://stackoverflow.com/questions/9646575/vertical-sum-of-a-binary-tree） –

看起来像在这里解决同样的问题。 http://stackoverflow.com/questions/9646575/vertical-sum-of-a-binary-tree – krishnakamathk

难道你不能在第一次遍历中做到这一切吗？定义从HD到sum的字典（散列图）。对于您访问的每个节点，将其值添加到正确的字典键 - 这是一个O(n)解决方案。

d = {} 

def traverse(node, hd): 
    if not node: 
    return 
    if not hd in d: 
    d[hd] = 0 
    d[hd] = d[hd] + node.value 
    traverse(node.left, hd - 1) 
    traverse(node.right, hd + 1)

然后就叫traverse(root, 0)

来源

2013-01-23 17:10:31

+1为真棒解决方案〜 – Chasefornone

感谢您的解决方案。用于实现此处 - http://k2code.blogspot.in/2011/12/vertical-sum-of-binary-tree.html :) – kinshuk4

这里是一个在C在返回的VSUM数组将有结果。

void vsum(struct tree *t, int vsum[], int depth)  { 

    if (t == NULL) 
     return; 

    vsum[depth] += t->val; 
    depth++; 

    vsum(t->left, vsum, depth); 
    vsum(t->right, vsum, depth); 

}

来源

2013-04-23 18:14:17

您应该检查depth是否是vsumand中的有效索引，并为其指定一个值0 – Syler

使用水平序遍历，使用具有元素和它们的相邻值HD一个队列。下面的算法将给出O（n）的方案无法运行测试]

void findVertSum(struct node *root) 
{ 
enqueue(root); 
enqueue(0); 
while(!isEmptyQueue()) 
{ 
    tempnode = dequeue(); 
    vertIndex = dequeue(); 

    sum[vertIndex] += tempnode->val; 
     // Array cant be used because there will be sum[-1], sum[-2] etc, which will give error. This line hense only gives the idea to store solution. 

    if(t->left) 
    { 
    enqueue(t->left); 
    enqueue(vertIndex - 1); 
    } 

    if(t->right) 
    { 
    enqueue(t->right); 
    enqueue(vertIndex + 1); 
    } 
}

来源

2014-07-10 17:53:44

这是我的解决方案，它运行在O（N）`

#include <iostream> 
#include <vector> 
using namespace std; 

vector<int> v; 
int size; 

typedef struct node 
{ 
int data; 
struct node *left, *right ; 
} node, *ptr; 



ptr newNode(int item) 
{ 
ptr temp = new node; 
temp->data = item; 
temp->left = temp->right = NULL; 
return temp; 
} 

void printVerticalSumUtil(ptr root, int line) 
{ 

if (root == NULL) return; 
else 
{ 

    v[line] += root->data; 
    printVerticalSumUtil(root->left, line - 1); 
    printVerticalSumUtil(root->right, line + 1); 
} 


} 

void printVerticalSum(ptr root) 
{ 
if (root == NULL) 
    return; 

//Calculating the line No for the root 
ptr curr = root; 
int line = 0; 
while (curr->left != NULL) 
{ 
    curr = curr->left; 
    line++; 
} 
size = 2 * line + 1; //Total No of Lines 
line++;  //Adjusting line no for root 

for (int i = 1; i <= size; ++i) //Initializing lines to zero 
    v.push_back(0); 

printVerticalSumUtil(root, line); 

for (int i = 1; i <= size; ++i) 
{ 
    cout << "Sum of Line " << i << " is " << v[i] << endl; 
} 
} 

int main() 
{ 

ptr root = newNode(1); 
root->left = newNode(2); 
root->right = newNode(3); 
root->left->left = newNode(4); 
root->left->right = newNode(5); 
root->right->left = newNode(6); 
root->right->right = newNode(7); 

printVerticalSum(root); 

return 0; 
}`

来源

2014-08-24 06:43:19 algo1

#define HD_OFFSET 16 

void vertical_sum(Node *node, int hd, int sum[], int *min, int *max){ 

/* We are offseting the index to access array correctly. 
Root will be at HD_OFFSET/2 index and all vertical lines on left will 
be at 0 to HD_OFFSET/2 and right side will be on HD_OFFSET/2 to HD_OFFSET */ 

int index = hd + HD_OFFSET/2; 

if(!node) return; 

/* to keep track of min and max index filled in sum array */ 
if(index > (*max)) (*max) = index; 
if(index < (*min)) (*min) = index; 

sum[index]+= node->value; 
/*If we are moving on the left side, 
we will pass index as one less the current */ 
vertical_sum(node->left, hd-1, sum, min, max); 

/*If we are moving on the right side, 
we will pass index as one more the current */ 
vertical_sum(node->right, hd+1, sum, min, max); 
}

来源

2015-03-25 11:11:08 jitsceait

对不起，我迟到解。有几种方法可以解决这个问题。 Itay Karo已经使用hashmap提供了一个很好的解决方案。您还可以使用双向链表链接列表：

开始根节点和空双列表listNode
的根节点的值添加到当前的listNode
现在，每当你向左走，通过listNode。 left和root.left并递归调用step1和2。
同样为右节点，通过listNode.right和root.right 下面是代码：

 
printVerticalSum(TreeNode root) 
{ 
    if(root==null) 
     return -1; 
    allocate node doubleLinkList //initialize, 
    printVerticalSumUtil(root, doubleLinkList); 
    //write the function to print double linked list 
    System.out.println(doubleLinkList.toString()) 
} 

printVerticalSumUtil(TreeNode root, ListNode listNode) { if(root==NULL) return; 

if(root.left!=NULL) if(listNode.prev!=NULL) listNode.prev.data += root.data; else ListNode t = new ListNode(root.data); t.next=listNode; listNode.prev = t; findVerticalSum(root.left, listNode.prev) 

if(root.right!=NULL) if(listNode.next!=NULL) listNode.next.data += root.data; else ListNode t = new ListNode(root.data); t.prev=listNode; listNode.next = t; findVerticalSum(root.right, listNode.next) }

更多细节在这里 - http://k2code.blogspot.in/2011/12/vertical-sum-of-binary-tree.html。谢谢。

来源

2016-03-13 06:55:58 kinshuk4

下面的代码将做的工作：

使用语言：Java的

// Algorithm for calculating the vertical sum of a binary tree. 
static void verticalSum(Node root, int[] sum, int index) 
{ 
    /* 
     The sum array contains the sum of each 
     vertical line starting from the leftmost vertical line. 
    */ 
    if(root==null) 
    { 
     return; 
    } 
    else 
    { 
     sum[index]+=(int)root.data; 
     verticalSum(root.left, sum, index-1); 
     verticalSum(root.right, sum, index+1); 
    } 
}

您需要使用下面的代码来调用上面的函数：

//Algorithm for calculating the vertical sum of a binary tree. 
int level=countLevels(root); 
int a=1,d=2,n=level; 
int sizeOfArray= a+(n-1)*d; 
int index=sizeOfArray/2; 
int[] sum=new int[sizeOfArray]; 
verticalSum(root, sum, index); 
System.out.print("Vertical Sum of the binary tree is : "); 
for(int i=0;i<sizeOfArray;i++) 
{ 
    System.out.print(", " + sum[i]); 
}

的countLevels（根）功能如下：

// Algorithm for calculating the number of levels 
static int countLevels(Node root) 
{ 
    int count=0,c=1,i=0,level=0; 
    Queue<Node> queue=new LinkedList<Node>(); 
    Node temp = null; 
    queue.add(root); 
    while(true) 
    { 
     if(queue.isEmpty()) 
     { 
      break; 
     } 
     level++; 
     for(i=0;i<c;i++) 
     { 
      temp=queue.remove(); 
      if(temp.left!=null) 
      { 
       queue.add(temp.left); 
       count++; 
      } 
      if(temp.right!=null) 
      { 
       queue.add(temp.right); 
       count++; 
      } 
     } 
     c=count; 
     count=0; 
    } 
    return level; 
}

来源

2016-11-24 17:54:37

//测试和工作示例

package tree; 

    import java.util.TreeMap; 

    public class VerticalSumProblem 
    { 

     public static void main(String[] args) 
     { 
      VerticalSumProblem verticalSum = new VerticalSumProblem(); 
      TreeNode treeNode = verticalSum.new TreeNode(1); 

      treeNode.left = verticalSum.new TreeNode(2); 
      treeNode.right = verticalSum.new TreeNode(3); 

      treeNode.left.left = verticalSum.new TreeNode(4); 
      treeNode.left.right = verticalSum.new TreeNode(5); 

      treeNode.right.left = verticalSum.new TreeNode(6); 
      treeNode.right.right = verticalSum.new TreeNode(7); 

      //treeNode.right.right.left =verticalSum.new TreeNode(8); 

      verticalSum.printTree(treeNode); 
      verticalSum.findVerticalSum(treeNode); 
     } 

     private void findVerticalSum(TreeNode root) 
     { 
      if(root == null) return; 

      TreeMap<Integer,Integer> _mappings = new TreeMap<Integer,Integer>(); 
      findVerticalSum(root,_mappings,0); 

      if (_mappings != null) 
      { 
       System.out.println(_mappings.entrySet()); 
      } 
     } 

     //if goes left -- and if goes right ++ 
     private void findVerticalSum(TreeNode treeNode,TreeMap<Integer,Integer> mappings, int level) 
     { 
      if(treeNode == null) return; 

      TreeNode treeNodeLeft,treeNodeRight; 

      if(treeNode.left != null) 
      { 
       treeNodeLeft = treeNode.left; 
       findVerticalSum(treeNodeLeft, mappings,level - 1); 
      } 

      int sum = mappings.get(level) == null ? 0 : mappings.get(level); 
      mappings.put(level, treeNode.data + sum); 

      if(treeNode.right != null) 
      { 
       treeNodeRight = treeNode.right; 
       findVerticalSum(treeNodeRight,mappings, level + 1); 
      } 
     } 



    /* Create following Binary Tree 
     1 
    / \ 
     2  3 
    /\ /\ 
    4 5, 6 7 

    */ 

     private void printTree(TreeNode treeNode) 
     { 
      TreeNode treeNodeLeft,treeNodeRight; 

      if(treeNode == null) return; 

      if(treeNode.left != null || treeNode.right != null) 
      { 
       treeNodeLeft = treeNode.left; 
       treeNodeRight = treeNode.right; 

       System.out.println("rootValue ="+treeNode.data); 

       System.out.println("Left child of ="+treeNode.data +" is : "+ getNodedata(treeNodeLeft)); 
       System.out.println("Right child of ="+treeNode.data+" is : "+ getNodedata(treeNodeRight)+"\n"); 

       printTree(treeNodeLeft); 
       printTree(treeNodeRight); 
      } 
     } 

     private int getNodedata(TreeNode treeNode) 
     { 
      if(treeNode != null) 
      { 
       return treeNode.data;  
      } 
      return -1; 
     } 

     private class TreeNode 
     { 
      private int data; 
      private TreeNode left,right; 

      TreeNode(int data) 
      { 
       this.data = data; 
       left = null; 
       right = null; 
      } 
     } 

    } 



    //vertical sum 
    /// | | | | | 
    // | | 1 | | 
    /// | 2 | 3 | 
    // 4 | 5,6 | 7 


    //    0 
    //   1  -1 
    //  2  0,0  -2 
    //

来源

2017-08-20 16:29:02 DeepakPanwar

这是我在C++简单的解决方法： - 这里我使用的地图存储从中心水平距离的基础总和。

Node *vsumprint(Node *root,int level,map<int,int> &mp){ 
    if(root==NULL)return NULL; 
    Node *temp = vsumprint(root->left,--level,mp); 
    if(temp==NULL){ 
     level++; 
    } 
    if(mp.find(level)!=mp.end()){ 
     mp[level] = root->data+mp[level]; 
    } 
    else{ 
     mp[level] = root->data+mp[level]; 
    } 
    return vsumprint(root->right,++level,mp); 
} 
void printVertical(Node *root) 
{ 
    map<int,int> mp; 
    vsumprint(root,0,mp); 
    for(auto it:mp){ 
     cout<<it.second<<" "; 
    } 

}

来源

2017-12-24 14:02:45 HeadAndTail

给定二叉树中的垂直和

回答

相关问题