二叉樹的打印右視圖  


難度級別 容易獎學金
經常問 ol石 土磚 亞馬遜 我的旅行 Snapdeal
二叉樹 樹遍歷

問題陳述  

問題“二叉樹的打印權限視圖”指出給您一棵二叉樹。 現在,您需要找到這棵樹的正確視圖。 在這裡,二叉樹的右視圖表示從正確的方向看時按樹的外觀打印序列。

例  

二叉樹的打印右視圖

2 7 4 6

解釋

如果您沿正確的方向觀察二叉樹。 我們只能看到輸出中打印的節點。 因為節點3和5分別隱藏在7和4的後面。

打印二叉樹右視圖的方法  

在此問題中,我們需要找到正確的視圖 二叉樹。 可以使用兩種方法解決該問題。 其中一個使用隊列,另一個使用遞歸。 首先,我們將討論使用隊列的方法。 因此,使用 隊列。 我們從二叉樹的根開始。 對於樹的每個級別,我們繼續將節​​點存儲在隊列中。 為了存儲下一層的節點,我們必須遍歷當前層的節點。 因此,當我們遍歷當前級別的節點時。 我們在此級別上打印最後一個節點。 當我們從右側觀察樹時。 我們唯一可見的節點是一個級別上最右邊的節點。 這種方法使用佔用空間的隊列。

也可以看看
兩個元素的頻率之間的最大差異,使得具有更大頻率的元素也更大

讓我們討論使用遞歸的解決方案。 解決方案與找到樹的左視圖非常相似。 用這種方法。 我們只是簡單地對樹進行遍歷,這與有序遍歷相反。 但是,我們還會跟踪當前的級別以及到目前為止所達到的最大級別。 當我們移至左側子樹之前的右側子樹時。 每當我們在樹中輸入新級別時。 我們首先遇到最右邊的節點。 因此,我們始終檢查當前級別是否大於最大級別,然後打印節點。 如果我們不考慮編譯器堆棧所需的空間,則此方法會更好。 如果我們確實考慮編譯器堆棧佔用的空間,則問題的空間複雜度取決於樹的高度。

推薦碼  

用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;
}

void printRightView(node* root, int level, int &max_level){
    if(root){
        if(level > max_level){
            max_level = level;
            cout << root->data <<" ";
        }
        printRightView(root->right, level+1, max_level);
        printRightView(root->left, level+1, max_level);
    }
}

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

  int max_level = 0;
  printRightView(root, 1, max_level);
}
2 7 4 6

Java代碼以打印二叉樹的右視圖

import java.util.*;

class node{
  int data;
  node left;
  node right;
}

class Main{
  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = null;
    tmp.right = null;
    return tmp;
  }

  static int max_level;
  static void printRightView(node root, int level){
      if(root != null){
          if(level > max_level){
              max_level = level;
              System.out.print(root.data+" ");
          }
          printRightView(root.right, level+1);
          printRightView(root.left, level+1);
      }
  }

  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);
    
    max_level = 0;
    printRightView(root, 1);
  }
}
2 7 4 6

複雜度分析  

時間複雜度

上), 我們只是遍歷樹中的節點。 因此,如果樹中有N個節點,則該算法需要O(N)個操作才能執行。

也可以看看
編寫代碼以確定兩棵樹是否相同

空間複雜度

O(1)。 如果不考慮編譯器堆棧使用的空間,則否則 哦) 需要空間。