# 給定二叉樹中的垂直和

## 問題陳述

“給定二叉樹中的垂直總和”問題指出您得到了一棵二叉樹，我們需要找到每個垂直水平的總和。 垂直水平，是指如果我們在左右方向上以1個單位的距離繪製垂直線，則與第ith條線相交的節點被稱為在第ii個垂直距離處。

## 例

```3, 5, 2, 5
```

## 推薦碼

### 給定二叉樹中垂直和的C ++代碼

```#include<bits/stdc++.h>
using namespace std;

struct node{
int data;
node *left;
node *right;
};

node* create(int data){
node *tmp = new node();
tmp->data = data;
tmp->left = tmp->right = NULL;
}

void fillVerticalSums(node *root,int horizontalLevel,map<int,int> &verticalSums){

// base case
if(!root)
return;
// recursively call for the left subtree
fillVerticalSums(root->left, horizontalLevel-1, verticalSums);
// add the value of current node to the current horizontal distance
verticalSums[horizontalLevel] += root->data;
// recursively call for right subtree
fillVerticalSums(root->right, horizontalLevel+1, verticalSums);
}

void verticalSum(node *root)
{
// map which stores the sum of nodes at each horizontal level
map<int, int> verticalSums;
fillVerticalSums(root, 0, verticalSums);
// map stores the data in sorted order
for(auto x: verticalSums)
cout<<x.second<<" ";
}

int main()
{
// here we have made a binary tree
node *root = create(1);
root->left = create(3);
root->right = create(2);
root->right->left = create(4);
root->right->right = create(5);
cout<<"The Vertical Sums: ";
verticalSum(root);

return 0;
}
```
`The Vertical Sums: 3 5 2 5`

### 給定二叉樹中垂直和的Java代碼

```import java.util.*;
// Class that denotes a node of the tree
class Node
{
int data;
Node left, right;

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

class Tree
{
static Node root;
static void fillVerticalSums(Node root, int horizontalLevel, TreeMap<Integer, Integer> verticalSums){

// base case
if(root == null)
return;
// recursively call for the left subtree
fillVerticalSums(root.left, horizontalLevel-1, verticalSums);
// add the value of current node to the current horizontal distance
if(verticalSums.containsKey(horizontalLevel))
verticalSums.put(horizontalLevel, verticalSums.get(horizontalLevel) + root.data);
else
verticalSums.put(horizontalLevel, root.data);
// recursively call for right subtree
fillVerticalSums(root.right, horizontalLevel+1, verticalSums);
}

static void verticalSum(Node root)
{
// map which stores the sum of nodes at each horizontal level
TreeMap<Integer, Integer> verticalSums = new TreeMap<Integer, Integer>();
fillVerticalSums(root, 0, verticalSums);
// map stores the data in sorted order
for(Map.Entry<Integer, Integer> entry: verticalSums.entrySet())
System.out.print(entry.getValue()+" ");
}

public static void main(String args[])
{
// here we have made a binary tree
Tree tree = new Tree();
tree.root = new Node(1);
tree.root.left = new Node(3);
tree.root.right = new Node(2);
tree.root.right.left = new Node(4);
tree.root.right.right = new Node(5);

System.out.print("The Vertical Sums: ");
verticalSum(tree.root);
}
}
```
`The Vertical Sums: 3 5 2 5`

## 複雜度分析

### 時間複雜度

O（N對數N）  因為我們僅遍歷了僅遍歷N個節點的樹。 而且自從插入，搜索和刪除以來，每項操作耗時N次。 這就是為什麼我們有一個log N因子的原因。