二叉树的打印右视图  


难度级别 易得奖学金
经常问 ol石 土砖 亚马逊 MakeMyTrip Snapdeal
二叉树 树遍历

问题陈述  

问题“二叉树的打印权限视图”指出给您一棵二叉树。 现在,您需要找到这棵树的正确视图。 在这里,二叉树的右视图表示从正确的方向看时按树的外观打印序列。

使用案列  

二叉树的打印右视图Pin

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)。 如果不考虑编译器堆栈使用的空间,则否则 哦) 需要空间。