http://www.geeksforgeeks.org/bottom-view-binary-tree/
Bottom View of a Binary Tree
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可以做到。
http://blog.****.net/zzran/article/details/41981969
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <limits.h>
using namespace std; void printArray(int *array, int size)
{
for(int i = ; i < size; i++)
cout << array[i]<< "\t" ;
cout << endl;
} void printVector(vector<int> array )
{
for(int i = ; i <array.size(); i++)
cout << array[i]<< "\t" ;
cout << endl;
} struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}; void preorder(TreeNode * root)
{
if(root == NULL) return;
cout << root->val << "\t" ;
preorder(root->left);
preorder(root->right);
} void inorder(TreeNode * root)
{
if(root == NULL) return;
inorder(root->left);
cout << root->val << "\t" ;
inorder(root->right);
} void postorder(TreeNode * root)
{
if(root == NULL) return;
postorder(root->left);
postorder(root->right);
cout << root->val << "\t" ;
} struct newNode
{
TreeNode* m_node;
int m_idx;
newNode(TreeNode* node, int idx)
{
m_node = node;
m_idx = idx;
}
}; class Solution {
public:
vector<int> bottomView(TreeNode* root) {
queue<newNode* > q1;
queue<newNode* > q2;
vector<int> res;
map<int, int> mapping;// index -- value pair if(root != NULL)
{
q1.push(new newNode(root, ));
} int leftMost = ;
int rightMost = ;
while(!q1.empty())
{
newNode * p = q1.front();
q1.pop(); mapping[p->m_idx] = p->m_node->val; if(p->m_idx < leftMost)
leftMost = p->m_idx;
if(p->m_idx > rightMost)
rightMost = p->m_idx; if(p->m_node->left)
q2.push(new newNode(p->m_node->left, p->m_idx - ) );
if(p->m_node->right)
q2.push(new newNode(p->m_node->right, p->m_idx + )); if(q1.empty() /*&& !q2.empty()*/)
{
swap(q1, q2);
}
} for(map<int, int>::iterator it = mapping.begin(); it != mapping.end(); it++)
{
cout << it->first <<"\t" <<it->second << endl;
}
for(int i = leftMost ; i <= rightMost ; i++)
res.push_back(mapping[i]);
return res;
} }; int main()
{
TreeNode node0();
TreeNode node1();
TreeNode node2();
TreeNode node3();
TreeNode node4();
TreeNode node5();
TreeNode node6(); node0.left = &node1;
node0.right= &node2; node1.left = &node3;
node1.right= &node4; node2.left = &node5;
node2.right= &node6; Solution sl;
vector<int> res = sl.bottomView(&node0); printVector(res);
cout << endl;
return ;
}
另外,top view也可以用这样的方法,不是保留最后一个,而是保留第一次idx的结构,后续的数据不保存。