二叉树的顶视图


难度级别 中等
经常问 亚马逊 Paytm Samsung 沃尔玛实验室
二叉树 深度优先搜索 树遍历

顶视图 二叉树 是当 从顶部查看。 给定一棵二叉树,该二叉树的输出顶视图从最左边的水平到最右边的水平。

使用案列

例如1

二叉树的顶视图

二叉树的顶视图

例如2

二叉树的顶视图

二叉树顶视图的解决方案类型

  1. DFS
  2. BFS

深度优先搜索(DFS)/有序遍历

二叉树顶视图的方法

我们执行二叉树的有序遍历,并跟踪遍历期间遇到的每个节点的垂直高度(h)和水平宽度(w)。

  • 如果是第一次访问特定的水平宽度级别,则我们将此水平级别(该节点的w值)映射到节点数据(将该节点存储在顶视图中)和该节点的垂直高度。 即地图[水平宽度->(node.data,垂直高度)]。
  • 如果已经访问过特定的水平宽度级别,那么我们将检查为该水平宽度映射的垂直高度(该节点的h值)。 如果当前节点的垂直高度小于映射的垂直高度(当当前节点垂直位于先前映射的节点上方并因此出现在叠加在先前映射的节点上的树的顶视图中时,就会发生这种情况),我们只需更改映射值当前水平宽度与{当前节点数据,当前节点水平高度}的关系。
  • 遍历结束后,只需按其水平级别的顺序输出顶视图节点值即可。

下面我们描述了二叉树的每个节点的{水平宽度,垂直高度}:

二叉树的顶视图

算法

  1. 创建一个映射来存储二叉树的顶视图。
  2. 执行二叉树的有序遍历。
  3. 在遍历期间,请跟踪每个树节点的垂直高度(h)和水平宽度(w)。
  4. 对于当前正在访问的节点,请检查其水平宽度级别是否已被访问。
  5. 如果尚未访问当前水平高度,则映射{当前水平宽度->(当前节点数据,当前垂直高度)}。
  6. 如果已经访问了当前的水平宽度水平,则进行比较 垂直高度值已映射 当前节点的垂直高度的当前水平高度。
    1. 如果 映射的垂直高度的值 大于当前节点的垂直高度(当当前节点垂直位于先前映射的节点上方并因此出现在树的顶视图中并叠加在先前映射的节点上时,会发生这种情况),只需更改当前水平宽度的映射值到{当前节点数据,当前垂直高度}。 即{当前水平宽度->(当前节点数据,当前垂直高度)}。
  7. 遍历后,只需输出存储在地图中的顶视图即可。

上面的算法描述如下:

二叉树的顶视图 二叉树的顶视图 二叉树的顶视图 二叉树的顶视图 二叉树的顶视图 二叉树的顶视图 二叉树的顶视图 二叉树的顶视图

二叉树顶视图的实现

C ++程序
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// defining the tree node
class Node
{
    public : 
    int data;
    Node *left;
    Node *right;
    
    // constructor for initialization
    Node(int num)
    {
        data = num;
        left = right = NULL;
    }
};

/* the function performs inorder traversal and stores top view
of the binary tree. 
for every node encountered during the traversal we have it's : 
w -> horizontal depth(width)
h -> vertical depth(height)
*/
void inorder(Node *root,int w,int h, map<int,pair<int,int>> &Map)
{ 
    if(root == NULL) 
    return; 
    
    inorder(root->left,w-1,h+1,Map);
  
    /* check if a particular horizontal level has been visited or not */
    if(Map.find(w) == Map.end())
        Map[w] = make_pair(root->data,h); 
    
    /* 
    if particular horizontal level has been visited 
    then check if height of current node is less than
    the previous node met at same horizontal level, if this 
    is true then the current node should replace previous node
    in top view of the binary tree */
    
    else if(Map[w].second>h)
        Map[w] = make_pair(root->data,h);
    
    inorder(root->right,w+1,h+1,Map); 
} 
  
/* function should print the topView of 
 the binary tree */ 
void topView(Node *root)
{ 
    if(root ==  NULL)
    return;
    
    /* map to store node at each vertical(horizontal) distance(Level)
    i.e. stores top view */
    map<int,pair<int,int>> Map; 
  
    // obtain top view of binary tree into the Map
    inorder(root,0,0,Map); 
    
    /* traverse the map and print top view */
    for(auto i : Map)
    cout<<i.second.first<<" ";
} 

// main function to implement above functions
int main() 
{
    /* construct the binary tree*/
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->right->right = new Node(5);
    root->left->right = new Node(4);
    root->left->right->right = new Node(6);
    root->left->right->right->right = new Node(7);
    root->left->right->right->right->right = new Node(8);
    
    topView(root);
    
    return 0;
}
2 1 3 5 8
Java程序
import java.io.*;
import java.util.*;

class tutorialCup 
{
    static class Node
    {
        int data;
        Node left;
        Node right;
        
        Node(int num)
        {
            data = num;
            left = right = null;
        }
    };
    // class definition to handle pairs
    static class pair
    {
        int nodeData;
        int height;
        
        pair(int key,int num)
        {
            nodeData = key;
            height = num;
        }
    }
    
    /* the function performs inorder traversal and stores top view
    of the binary tree. 
    for every node encountered during the traversal we have it's : 
    w -> horizontal depth(width)
    h -> vertical depth(height)
    */
    static void inorder(Node root,int w,int h, TreeMap <Integer,pair> Map)
    { 
        if(root == null) 
        return; 
        
        inorder(root.left,w-1,h+1,Map);
        
        /* check if a particular horizontal level has been visited or not */
        if(!Map.containsKey(w))
            Map.put(w,new pair(root.data,h)); 
        
        /* if particular horizontal level has been visited 
        then check if height of current node is less than
        the previous node met at same horizontal level, if this 
        is true then the current node should replace previous node
        in top view of the binary tree */
        else if(Map.get(w).height > h)
            Map.put(w,new pair(root.data,h));
        
        inorder(root.right,w+1,h+1,Map); 
    } 
      
    /* function should print the topView of 
     the binary tree */ 
    static void topView(Node root)
    { 
        if(root == null)
        return;
        
        /* map to store node at each vertical(horizontal) distance(Level)
        i.e. stores top view */
        TreeMap<Integer,pair> Map = new TreeMap<>();
      
        // obtain top view of binary tree into the Map
        inorder(root,0,0,Map); 
        
        /* traverse the map and print top view */
        for (Map.Entry<Integer, pair> i : Map.entrySet()) 
            System.out.print(i.getValue().nodeData+" ");
    } 
    
    /* main function to implement above function */
    public static void main (String[] args) 
    {
        /* construct the binary tree */
        Node root = new Node(1);  
        root.left = new Node(2);
        root.right = new Node(3);
        root.right.right = new Node(5);
        root.left.right = new Node(4);
        root.left.right.right = new Node(6);
        root.left.right.right.right = new Node(7);
        root.left.right.right.right.right = new Node(8);
        
        topView(root);
    }
}
2 1 3 5 8

二叉树顶视图的复杂度分析

  1. 时间复杂度:T(n)= O(n)
  2. 空间复杂度:A(n)= O(n),当树倾斜时会获得最坏的情况。

广度优先搜索(BFS)/级别顺序遍历

二叉树顶视图的方法

我们执行二叉树的BFS。 这种方法背后的想法是,在BFS期间,将遍历树的特定水平级别,然后再遍历以下所有水平级别,因此,我们不必跟踪每个树节点的垂直高度。 我们只需跟踪每个树节点的水平深度/宽度。

我们执行 BFS 遍历树。 在遍历期间,如果尚未访问当前节点的水平宽度,则我们只需将当前水平级别映射到当前节点数据即可。 即{当前水平->当前节点数据}。 该映射存储在树形图中。 遍历结束时,我们仅输出存储在地图中的顶视图。

下面我们描述了二叉树的每个节点的{水平宽度,垂直高度}:

算法

  1. 创建一个队列,该队列存储BFS遍历的节点及其相应的水平宽度。
  2. 创建一个映射,该映射存储二叉树的顶视图,其中键是水平宽度,映射的值是节点数据。
  3. 执行给定二叉树的BFS遍历。
  4. 对于当前正在访问的节点,请检查其水平宽度是否已被访问。
  5. 如果是第一次访问其水平宽度,则只需将当前水平宽度映射到当前节点数据即可。
  6. 遍历后,输出存储在地图中的顶视图。

以上 算法 如下所示:

二叉树顶视图的实现

C ++程序
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// defining the tree node
class Node
{
    public : 
    int data;
    Node *left;
    Node *right;
    
    // constructor for initialization
    Node(int num)
    {
        data = num;
        left = right = NULL;
    }
};

// function to obtain top-view of the binary tree
void topView(Node *root)
{
    if(root == NULL)
    return;
    
    /* map to store node at each vertical(horizontal) distance(Level)
    i.e. stores top view */
    map<int,int> Map;
    queue<pair<Node*,int>> q;
    
    q.push({root,0});
    
    // obtain top view of binary tree into the Map
    while(!q.empty())
    {
        auto top = q.front();
        q.pop();
        
        Node *curr = top.first;
        int horizontalLevel = top.second;
        
        /* if the current horizontal Level has not been
        visited then the first node encountered at this horizontal 
        level during level order traversal should be displayed 
        in top view of the tree */
        if(Map.find(horizontalLevel) == Map.end())
        Map[horizontalLevel] = curr->data;
        
        if(curr->left)
        q.push({curr->left,horizontalLevel-1});
        
        if(curr->right)
        q.push({curr->right,horizontalLevel+1});
    }
    
    // print the top view in order of horizontal Level
    for(auto i : Map)
    cout<<i.second<<" ";
}

// main function to implement above functions
int main() 
{
    /* construct the binary tree*/
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->right->right = new Node(5);
    root->left->right = new Node(4);
    root->left->right->right = new Node(6);
    root->left->right->right->right = new Node(7);
    root->left->right->right->right->right = new Node(8);
    
    topView(root);    
    return 0;
}
2 1 3 5 8
Java程序
import java.io.*;
import java.util.*;

class tutorialCup 
{
    static class Node
    {
        int data;
        Node left;
        Node right;
        
        Node(int num)
        {
            data = num;
            left = right = null;
        }
    };
    // class definition to handle pairs
    static class pair
    {
        int nodeData;
        int height;
        
        pair(int key,int num)
        {
            nodeData = key;
            height = num;
        }
    }
    
    /* the function performs inorder traversal and stores top view
    of the binary tree. 
    for every node encountered during the traversal we have it's : 
    w -> horizontal depth(width)
    h -> vertical depth(height)
    */
    static void inorder(Node root,int w,int h, TreeMap <Integer,pair> Map)
    { 
        if(root == null) 
        return; 
        
        inorder(root.left,w-1,h+1,Map);
        
        /* check if a particular horizontal level has been visited or not */
        if(!Map.containsKey(w))
            Map.put(w,new pair(root.data,h)); 
        
        /* if particular horizontal level has been visited 
        then check if height of current node is less than
        the previous node met at same horizontal level, if this 
        is true then the current node should replace previous node
        in top view of the binary tree */
        else if(Map.get(w).height > h)
            Map.put(w,new pair(root.data,h));
        
        inorder(root.right,w+1,h+1,Map); 
    } 
      
    /* function should print the topView of 
     the binary tree */ 
    static void topView(Node root)
    { 
        if(root == null)
        return;
        
        /* map to store node at each vertical(horizontal) distance(Level)
        i.e. stores top view */
        TreeMap<Integer,pair> Map = new TreeMap<>();
      
        // obtain top view of binary tree into the Map
        inorder(root,0,0,Map); 
        
        /* traverse the map and print top view */
        for (Map.Entry<Integer, pair> i : Map.entrySet()) 
            System.out.print(i.getValue().nodeData+" ");
    } 
    
    /* main function to implement above function */
    public static void main (String[] args) 
    {
        /* construct the binary tree */
        Node root = new Node(1);  
        root.left = new Node(2);
        root.right = new Node(3);
        root.right.right = new Node(5);
        root.left.right = new Node(4);
        root.left.right.right = new Node(6);
        root.left.right.right.right = new Node(7);
        root.left.right.right.right.right = new Node(8);
        
        topView(root);
    }

}
2 1 3 5 8

二叉树顶视图的复杂度分析

  1. 时间复杂度:T(n)= O(n)
  2. 空间复杂度:A(n)= O(n),当树倾斜时会获得最坏的情况。

參考資料