按垂直順序打印二叉樹


難度級別
經常問 ol石 亞馬遜 BrowserStack 戴爾 Flipkart 雜貨店 我的旅行 內斯科普 沃爾瑪實驗室
哈希 樹遍歷

在此問題中,我們給出了一個指針,該指針表示根的根。 二叉樹 您的任務是按垂直順序打印二叉樹。

輸入

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

產量

4
2
電話: 1 5 6
3 8th Street, Suite XNUMX
7
9

解釋

按垂直順序打印二叉樹

垂直順序打印二叉樹的算法

  1. 將元素插入不同的節點。
  2. 將距離設置為0。
  3. 如果根為true,則檢查根是否等於null,然後返回。
  4. 將keyValue設置為distance的值作為地圖中的關鍵點。
    1. 檢查是否 “核心價值” 等於null。
      1. 如果為true,則初始化一個 “核心價值” 到新向量,並在該向量中添加根值(元素)。
    2. 否則,在該向量中添加根值,因為它已經存在。
  5. 把距離和 “核心價值” 在地圖上。
  6. 用以下命令遞歸調用printVerticalTree函數 “ root.left”,距離-1, “m”個“ root.right”,距離+1, “m”個 分別用於左和右子樹。
  7. 打印地圖。

以垂直順序打印二叉樹的說明

我們以垂直順序打印二叉樹的主要思想是,以每次傳遞的更新值作為參數遞歸地調用函數,並根據所需輸出不斷更新地圖。

從在root,root.right,root.left,root.left.left等處插入節點開始,我們將值作為輸入。 我們需要從樹中最左邊的元素開始一個接一個地接受這些輸入。 我們初始化一個向量,然後使用整數作為向量的每個索引的鍵將其插入到地圖中。 在向量中,我們將垂直存儲所有值,然後將距離和keyValue作為 “核心價值” 對。

主要部分

當我們第一次傳遞根時,它沒有空值。 然後map.get(distance)將存儲在keyValue中,如果發現keyValue為null表示在地圖中作為key的“距離”它沒有任何值,則我們初始化向量keyValue並添加根。鍵,表示root.key所指示的元素。 如果keyValue不為null,則意味著已經有一些現有值存儲在其“鍵”中。 我們只需要添加該“ root.key”(所指示的元素)即可。

在所有這些中,還有一個更重要的術語是距離。 距離是指樹中任何節點到根節點的垂直距離,我們得到數字作為距離,左邊的子樹得到負數,右邊的子樹得到正數,右邊的根和下面的節點被認為距根的距離為0,這是我們遞歸地傳遞給我們的距離。 每次我們將distance作為參數傳遞時,這意味著我們將與之一起存儲一些值,這些值被證明是地圖中的鍵,例如本例中的-2,-1、0、1、2 3.這些是我們要在其中存儲元素的每個向量的鍵。

我們需要從映射中打印值,映射中的所有值都具有鍵(已排序),鍵從最左側的元素-2到3(即最右側的元素)開始。 我們將垂直獲取所有元素並進行打印。

以垂直順序打印二叉樹的實現

C ++程序

#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct Node
{
    int key;
    Node *left, *right;
};
struct Node* newNode(int key)
{
    struct Node* node = new Node;
    node->key = key;
    node->left = node->right = NULL;
    return node;
}
void printVerticalTree(Node* root, int distance, map<int, vector<int>> &mymap)
{
    if (root == NULL)
        return;

    mymap[distance].push_back(root->key);

    printVerticalTree(root->left, distance-1, mymap);

    printVerticalTree(root->right, distance+1, mymap);
}
void printVerticalOrder(Node* root)
{
    map < int,vector<int> > mymap;
    int distance = 0;
    printVerticalTree(root, distance,mymap);
    map< int,vector<int> > :: iterator it;
    for (it=mymap.begin(); it!=mymap.end(); it++)
    {
        for (int i=0; i<it->second.size(); ++i)
            cout << it->second[i] << " ";
        cout << endl;
    }
}
int main()
{
    Node *root = newNode(3);
    root->left = newNode(4);
    root->right = newNode(6);
    root->left->left = newNode(8);
    root->left->right = newNode(11);
    root->right->left = newNode(14);
    root->right->right = newNode(17);
    root->right->left->right = newNode(18);
    root->right->right->right = newNode(25);
    cout << "Vertical order traversal is \n";
    printVerticalOrder(root);
    return 0;
}
Vertical order traversal is
8
4
3 11 14
6 18
17
25

Java程序

import java.util.TreeMap;
import java.util.Vector;
import java.util.Map.Entry;

class printBinarytreeVertical
{
    static class Node
    {
        int key;
        Node left;
        Node right;
        Node(int data)
        {
            key = data;
            left = null;
            right = null;
        }
    }
    static void printVerticalTree(Node root, int distance, TreeMap<Integer,Vector<Integer>> map)
    {

        if(root == null)
        {
            return;
        }
        Vector<Integer> keyValue = map.get(distance);
        if(keyValue == null)
        {
            keyValue = new Vector<>();
            keyValue.add(root.key);
        }
        else
            keyValue.add(root.key);

        map.put(distance, keyValue);

        printVerticalTree(root.left, distance-1, map);

        printVerticalTree(root.right, distance+1, map);
    }
    static void printVerticalOrder(Node root)
    {
        TreeMap<Integer,Vector<Integer>> m = new TreeMap<>();
        int distance =0;
        printVerticalTree(root,distance,m);
        for (Entry<Integer, Vector<Integer>> getentry : m.entrySet())
        {
            System.out.println(getentry.getValue());
        }
    }
    public static void main(String[] args)
    {
        Node root = new Node(3);
        root.left = new Node(4);
        root.right = new Node(6);
        root.left.left = new Node(8);
        root.left.right = new Node(11);
        root.right.left = new Node(14);
        root.right.right = new Node(17);
        root.right.left.right = new Node(18);
        root.right.right.right = new Node(25);
        System.out.println("Vertical Order traversal is");
        printVerticalOrder(root);
    }
}
Vertical Order traversal is
[8]
[4]
[3, 11, 14]
[6, 18]
[17]
[25]

垂直順序打印二叉樹的複雜度分析

時間複雜度

O(n登錄) 哪裡 “ n” 是樹中元素的數量。

空間複雜度

O(N) 哪裡 “ n” 是樹中元素的數量。

參考