二叉树的底视图  


难度级别 易得奖学金
经常问 ol石 亚马逊 优惠券 Flipkart Paytm 沃尔玛实验室
二叉树 树遍历

问题陈述  

问题“二叉树的底视图”指出您已获得一棵二叉树,现在需要查找给定树的底视图 。 当我们从向下的方向看到一棵树时。 我们可见的节点是二叉树的底视图。

使用案列  

二叉树的底视图

5 6 4 7

途径  

该方法很简单,因为我们已经解决了与此类似的问题。 问题二叉树的俯视图与此类似,我们必须从上述方向打印对我们可见的节点。 那么我们如何解决这个问题呢?

我们需要在这里使用水平距离的概念。 每当我们向节点的左方向移动时,我们都会从当前节点的水平距离中减去。 同样,如果我们向右移动,我们会将水平距离加1。 一旦我们熟悉了这个概念。 我们将使用地图跟踪每个水平距离的节点。 然后,我们将遍历该树,并在找到节点时更新地图。 我们将水平距离作为关键点,将节点作为地图的值。 因此,使用水平顺序遍历,继续计算水平距离并更新 地图.

完成所有这些计算后,只需在地图中打印元素即可。 因为最左边的节点具有最大的负水平距离,而最右边的节点具有最高的正值。

参见
从链接列表表示构造完整的二叉树

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>();
      Queue<node> q = new LinkedList<node>();
      q.add(root);
      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;
          	q.add(now.left);
          }
          if(now.right != null){
          	now.right.hd = now.hd + 1;
          	q.add(now.right);
          }
      }
      for(Map.Entry<Integer, Integer> entry : m.entrySet())
          System.out.print(entry.getValue()+" ");
  }
}
5 6 4 7

复杂度分析  

时间复杂度

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

空间复杂度

上),最后一级最多(N + 1)/ 2。 因此,空间复杂度是线性的。