对于二叉树，我们定义水平距离如下：
Horizontal distance(hd) of root = 0
If you go left then hd = hd(of its parent)-1, and
if you go right then hd = hd(of its parent)+1.
然后树的底部视图由树的所有节点组成，其中没有具有相同hd和更高级别的节点。 （对于给定的hd值，可能有多个这样的节点。在这种情况下，它们都属于底部视图。）我正在寻找一种输出树的底部视图的算法。
例子：
假设二叉树是：
1
/ \
2 3
/ \ / \
4 5 6 7
\
8
树的底部视图是：4 2 5 6 8 7
Ok so for the first example,
Horizontal distance of node with value 1: 0, level = 1
Horizontal distance of node with value 2: 0 - 1 = -1, level = 2
Horizontal distance of node with value 3: 0 + 1 = 1, level = 2
Horizontal distance of node with value 4: -1 - 1 = -2, level = 3
Horizontal distance of node with value 5: -1 + 1 = 0, level = 3
Horizontal distance of node with value 6: 1 - 1 = 0, level = 3
Horizontal distance of node with value 7: 1 + 1 = 2, level = 3
Horizontal distance of node with value 8: 0 + 1 = 1, level = 4
So for each vertical line that is for hd=0, print those nodes which appear in the last level of that line.
So for hd = -2, print 4
for hd = -1, print 2
for hd = 0, print 5 and 6 because they both appear in the last level of that vertical line
for hd = 1, print 8
for hd = 2, print 7
还有一个例子供参考：
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \ / \ / \
8 9 10 11 12 13 14 15
因此，此输出将为：8 4 9 10 12 5 6 11 13 14 7 15
Similarly for this example
hd of node with value 1: 0, , level = 1
hd of node with value 2: -1, level = 2
hd of node with value 3: 1, level = 2
hd of node with value 4: -2, level = 3
hd of node with value 5: 0, , level = 3
hd of node with value 6: 0, level = 3
hd of node with value 7: 2, level = 3
hd of node with value 8: -3, level = 4
hd of node with value 9: -1, level = 4
hd of node with value 10: -1, level = 4
hd of node with value 11: 1, level = 4
hd of node with value 12: -1, level = 4
hd of node with value 13: 1, level = 4
hd of node with value 14: 1, level = 4
hd of node with value 15: 3, level = 4
So, the output will be:
hd = -3, print 8
hd = -2, print 4
hd = -1, print 9 10 12
hd = 0, print 5 6
hd = 1, print 11 13 14
hd = 2, print 7
hd = 3, print 15
So the ouput will be:
8 4 9 10 12 5 6 11 13 14 7 15
我已经知道一种方法，我可以使用大量的额外空间（一个地图和一个用于存储垂直线中最后一个元素的水平的一维数组）并且时间复杂度为$ O（N \记录N）$。这是此方法的实现：
#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
using namespace std;
struct Node{
int data;
struct Node *left, *right;
};
Node* newNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
int height(Node *node)
{
if(node == NULL)
return 0;
else{
int lh = height(node->left);
int rh = height(node->right);
if(lh > rh)
return (lh+1);
else
return (rh+1);
}
}
void printBottom(Node *node, int level, int hd, int min, map< int, vector<int> >& visited, int lev[], int l)
{
if(node == NULL)
return;
if(level == 1){
if(lev[hd-min] == 0 || lev[hd-min] == l){
lev[hd-min] = l;
visited[hd-min].push_back(node->data);
}
}
else if(level > 1)
{
printBottom(node->left, level-1, hd-1, min, visited, lev, l);
printBottom(node->right, level-1, hd+1, min, visited, lev, l);
}
}
void findMinMax(Node *node, int *min, int *max, int hd)
{
if(node == NULL)
return;
if(hd < *min)
*min = hd;
else if(hd > *max)
*max = hd;
findMinMax(node->left, min, max, hd-1);
findMinMax(node->right, min, max, hd+1);
}
int main()
{
Node *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);
root->left->left->left = newNode(8);
root->left->left->right = newNode(9);
root->left->right->left = newNode(10);
root->left->right->right = newNode(11);
root->right->left->left = newNode(12);
root->right->left->right = newNode(13);
root->right->right->left = newNode(14);
root->right->right->right = newNode(15);
int min = 0, max = 0;
findMinMax(root, &min, &max, 0);
int lev[max-min+1];
map < int, vector<int> > visited;
map< int,vector<int> > :: iterator it;
for(int i = 0; i < max-min+1; i++)
lev[i] = 0;
int h = height(root);
for (int i=h; i>0; i--){
printBottom(root, i, 0, min, visited, lev, i);
}
for(it = visited.begin() ; it != visited.end() ; it++) {
for(int i=0 ; i < it->second.size() ; i++) {
cout << it->second[i] << " ";
}
}
return 0;
}
我正在寻求帮助，以更优化的方式做到这一点，使用更少的空间或时间。有没有其他有效的方法来解决这个问题？
首先，您可以将时间复杂度降低到O（n），同时保持相同的空间复杂度。你可以通过在一次visited中填充printBottom来做到这一点：
void printBottom(Node *node, int level, int hd, int min, map< int, vector<int> >& visited, int lev[])
{
if(node == NULL)
return;
if(lev[hd-min] < level){
lev[hd-min] = level;
visited[hd-min] = new vector<int>; //erase old values, they are hidden by the current node
}
if(lev[hd-min] <= level){
visited[hd-min].push_back(node->data);
}
printBottom(node->left, level+1, hd-1, min, visited, lev);
printBottom(node->right, level+1, hd+1, min, visited, lev);
}
最初的电话printBottom(root, 1, 0, min, visited, lev);
如果你按照增加hd值的顺序坚持节点beig输出，我认为你不能提高空间消耗。但是，如果你允许不同的输出顺序，你可以摆脱visited，首先确定'hd'的每个值，输出哪个级别然后再进行另一次传递，打印匹配的值：
void fillLev(Node *node, int level, int hd, int min, int lev[])
{
if(node == NULL)
return;
if(lev[hd-min] < level){
lev[hd-min] = level;
}
fillLev(node->left, level+1, hd-1, min, lev);
fillLev(node->right, level+1, hd+1, min, lev);
}
void printBottom(Node *node, int level, int hd, int min, int lev[])
{
if(node == NULL)
return;
if(lev[hd-min] == level){
cout << node->data;
}
printBottom(node->left, level+1, hd-1, min, lev);
printBottom(node->right, level+1, hd+1, min, lev);
}
打电话给fillLev(root, 1, 0, min, lev);和printBottom(root, 1, 0, min, lev);。
void bottomView(node *root)
{
if(!root)
return ;
bottomView(root->left);
if(!root->left || !root->right)
cout<<"\t"<<root->data;
if ((root->right && !root->right->left) && (root->left &&!root->left->right))
cout<<"\t"<<root->data;
bottomView(root->right);
}
java中的解决方案如下，
呼叫电话会是，
boolean obstructionFromLeftSide = printBottomViewOrderOfTree(root.left, true);
boolean obstructionFromRightSide = printBottomViewOrderOfTree(root.right, false);
if (!(obstructionFromLeftSide || obstructionFromRightSide))
out.println(root.data + " ");
和功能在这里给出，
boolean printBottomViewOrderOfTree(Node root, boolean fromLeftSide)
{
if (root == null)
return false;
boolean obstructionFromLeftSide = printBottomViewOrderOfTree(root.left, true);
boolean obstructionFromRightSide = printBottomViewOrderOfTree(root.right, false);
if (!(obstructionFromLeftSide || obstructionFromRightSide))
out.println(root.data + " ");
if (fromLeftSide)
{
return root.right != null;
}
else
{
return root.left != null;
}
}
您是否考虑过基于水平距离和水平使用HashMap？在C ++中，我们可以像这样使用HashMap：
map<int,map<int,vector<int>>> HM;
// Let Horizontal Distance = HD,Level = L
// HM[HD][L] -> Vector tracking every node for a given HD,L
这种方法有Time = O（n），并且在删除笨拙的fillLev（）函数时对代码有所改进。我们在这里所做的只是单树遍历和单个hashmap遍历。这是代码：
void getBottomView(struct node *tree,int HD,int L,map<int,map<int,vector<int>>> &HM)
{
if(tree==NULL)
return;
HM[HD][L].push_back(tree->data);
getBottomView(tree->left,HD-1,L+1,HM);
getBottomView(tree->right,HD+1,L+1,HM);
}
void printBottomViewbyMap(map<int,map<int,vector<int>>> &HM)
{
map<int,map<int,vector<int>>>::iterator i;
for(i=HM.begin() ; i!=HM.end() ; i++)
{
if(i->second.size()==1)
{
map<int,vector<int>>::iterator mapi;
mapi = i->second.begin();
for(int j=0 ; j<= mapi->second.size()-1 ; j++)
cout<<mapi->second[j]<<" ";
}
else
{
map<int,vector<int>>::reverse_iterator mapi;
mapi = i->second.rbegin();
for(int j=0 ; j<= mapi->second.size()-1 ; j++)
cout<<mapi->second[j]<<" ";
}
}
}
void printBottomView(struct node *tree)
{
map<int,map<int,vector<int>>> HM;
getBottomView(tree,0,0,HM);
printBottomViewbyMap(HM);
}
如果仔细查看算法，则只能逐步到达更高水平的节点。如果我们有一个数组（我们不能因为负水平距离），我们只需要做一个[horizontalDistance] =节点。
然后遍历此数组以打印底部视图。
这可以工作，因为数组将存储特定水平距离的最底部元素，因为我们正在进行级别顺序遍历。
现在再解决负面索引问题，创建一个名为BiDirectionalList的类。在java中，您可以使用两个ArrayLists，或者在C ++中，您可以使用两个std :: vectors。
但是这里是您需要编码的BiDirectionalList：
public class BiDirectionalList<T> {
List<T> forward;
List<T> reverse;
public BiDirectionalList() {
forward = new ArrayList<>();
reverse = new ArrayList<>();
reverse.add(null); //0 index of reverse list will never be used
}
public int size() {
return forward.size() + reverse.size()-1;
}
public boolean isEmpty() {
if (forward.isEmpty() && reverse.size() == 1) return true;
return false;
}
public T get(int index) {
if (index < 0) {
reverse.get(-index);
}
return forward.get(index);
}
/**
* Sets an element at given index only if the index <= size.
* i.e. either overwrites an existing element or increases the size by 1
* @param index
* @param element
*/
public void set(int index, T element) {
if (index < 0) {
index = -index;
if (index > reverse.size()) throw new IllegalArgumentException("Index can at max be equal to size");
else if (reverse.size() == index ) reverse.add(index, element);
else reverse.set(index, element);
} else {
if (index > forward.size()) throw new IllegalArgumentException("Index can at max be equal to size");
else if (forward.size() == index ) forward.add(index, element);
else forward.set(index, element);
}
}
}
这里我们必须记录树的水平和从根节点的水平距离的记录。
void printBottom(Node *root,int dif,int level,map<int, pair<int,int> > &map){
if(root==NULL)return;
if(map.find(dif)==map.end() || level>= map[dif].second){
map[dif] = {root->data,level};
}
printBottom(root->left,dif-1,level+1,map);
printBottom(root->right,dif+1,level+1,map);
}
void bottomView(Node *root){
map<int ,pair<int,int> > map;
printBottom(root,0,0,map);
for(auto it : map){
printf("%d ",it.second.first);
}
}