# 二叉树的底视图

## 使用案列

`5 6 4 7`

## C ++代码打印二叉树的底部视图

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

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

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

int main(){
node *root = create(2);
root->left = create(3);
root->right = create(7);
root->left->left = create(5);
root->left->right = create(4);
root->left->right->left = create(6);

map<int,int> m;
queue<pair<int,node*>> q;
q.push(make_pair(0, root));
m[0] = root->data;
while(!q.empty()){
pair<int, node*> now = q.front();
q.pop();

m[now.first] = now.second->data;
if(now.second->left)
q.push(make_pair(now.first - 1, now.second->left));
if(now.second->right)
q.push(make_pair(now.first + 1, now.second->right));
}
for(auto x: m)
cout<<x.second<<" ";
}
```
`5 6 4 7`

## Java代码以打印二叉树的底部视图

```import java.util.*;

class node{
int data;
node left, right;
int hd;
}

class Main{

static node create(int data){
node tmp = new node();
tmp.data = data;
tmp.left = tmp.right = null;
tmp.hd = 0;
return tmp;
}

public static void main(String[] args){
node root = create(2);
root.left = create(3);
root.right = create(7);
root.left.left = create(5);
root.left.right = create(4);
root.left.right.left = create(6);

Map<Integer, Integer> m = new TreeMap<Integer, Integer>();
m.put(root.hd, root.data);
while(!q.isEmpty()){
node now = q.remove();

m.put(now.hd, now.data);
if(now.left != null){
now.left.hd = now.hd - 1;
}
if(now.right != null){
now.right.hd = now.hd + 1;
}
}
for(Map.Entry<Integer, Integer> entry : m.entrySet())
System.out.print(entry.getValue()+" ");
}
}```
`5 6 4 7`

## 复杂度分析

### 时间复杂度

O（NlogN），因为我们遍历了树并更新了值。 因为我们使用了映射，所以插入，删除和搜索是在O（logN）时间完成的。