c++ - 打印二叉树的底部 View

Question

对于二叉树，我们定义水平距离如下:

    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.

然后树的底部 View 由树的所有节点组成，其中没有具有相同hd 和更高级别的节点。 (对于给定的 hd 值，可能有多个这样的节点。在这种情况下，它们都属于底部 View 。)我正在寻找一种输出树底部 View 的算法。

---

例子:

假设二叉树是:

         1
        /  \
       2    3
      / \  / \
     4   5 6  7
            \
             8

树的底 View 是: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

---

我已经知道一种方法，我可以使用大量额外空间(一张 map 和一个一维数组来存储该垂直线上最后一个元素的级别)并且时间复杂度为 $O (N\log 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;
}

我正在寻求帮助以更优化的方式执行此操作，该方式占用的空间或时间更少。这个问题还有其他有效的方法吗？

Answer 1

首先，您可以将时间复杂度降低到 O(n)，同时保持相同的空间复杂度。您可以通过在 printBottom 的单次运行中填充 visited 来完成此操作:

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);。