Given a Binary Tree, we need to print the bottom view from left to right. A node x is there in output if x is the bottommost node at its horizontal distance. Horizontal distance of left child of a node x is equal to horizontal distance of x minus 1, and that of right child is horizontal distance of x plus 1.

Examples:

                      20
                    /                      8       22
                /   \                    5      3      25
                    / \      
                  10    14

For the above tree the output should be 5, 10, 3, 14, 25.

If there are multiple bottom-most nodes for a horizontal distance from root, then print the later one in level traversal. For example, in the below diagram, 3 and 4 are both the bottom-most nodes at horizontal distance 0, we need to print 4.

                   
                      20
                    /                      8       22
                /   \    /                 5      3 4     25
                    / \      
                  10    14 

For the above tree the output should be 5, 10, 4, 14, 25.

解决思路：算出二叉树最左边节点的距离，在算出二叉树最右边节点的距离，可以得出这棵二叉树所有节点的距离范围，如果根节点的水平距离为9，那么上边两个二叉树的距离范围是[-2, 2]。也就是说，输出节点应该有5个。那么怎么算每个节点的水平距离？首先要层次遍历二叉树，根据规则，根节点的左边孩子的水平距离是根节点水平距离减1，根节点右边孩子水平距离是根节点水平距离加1，层次遍历二叉树过程中，就算出了每个节点的水平距离，但是要求输出的水平距离只对应一个节点，所以要留下水平距离值相同的最后一个节点，用map可以做到。

#include <map>
#include <vector>
#include <iostream>

using namespace std;

typedef struct TreeNode {
	int data;
	struct TreeNode* lchild;
	struct TreeNode* rchild;
}TreeNode;

TreeNode* createNode(int data) {
	TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
	if (NULL == node)
		return NULL;
	node->data = http://www.mamicode.com/data;>

Bottom View of a Binary Tree