原文:
给定一个二叉树，打印它的右视图。二叉树的右视图是从右侧访问树时可见的一组节点。
right view of following tree is 1 3 7 8
1
/ \
2 3
/ \ / \
4 5 6 7
\
8
这个问题可以用简单的递归遍历来解决。我们可以通过向所有递归调用传递一个参数来跟踪节点的级别。这个想法也是为了跟踪最高水平。并以访问右子树先于访问左子树的方式遍历树。每当我们看到一个节点的级别超过目前为止的最大级别，我们就打印该节点，因为这是其级别中的最后一个节点(注意，我们在左子树之前遍历右子树)。下面是这种方法的实现。
c
// c program to print right view of binary tree
#include
using namespace std;
struct node
{
int data;
struct node *left, *right;
};
// a utility function to
// create a new binary tree node
struct node *newnode(int item)
{
struct node *temp = (struct node *)malloc(
sizeof(struct node));
temp->data = item;
temp->left = temp->right = null;
return temp;
}
// recursive function to print
// right view of a binary tree.
void rightviewutil(struct node *root,
int level, int *max_level)
{
// base case
if (root == null) return;
// if this is the last node of its level
if (*max_level < level)
{
cout << root->data << "\t";
*max_level = level;
}
// recur for right subtree first,
// then left subtree
rightviewutil(root->right, level 1, max_level);
rightviewutil(root->left, level 1, max_level);
}
// a wrapper over rightviewutil()
void rightview(struct node *root)
{
int max_level = 0;
rightviewutil(root, 1, &max_level);
}
// driver code
int main()
{
struct node *root = newnode(1);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(4);
root->left->right = newnode(5);
root->right->left = newnode(6);
root->right->right = newnode(7);
root->right->right->right = newnode(8);
rightview(root);
return 0;
}
// this code is contributed by shubhamsingh10
c
// c program to print right view of binary tree
#include
#include
struct node
{
int data;
struct node *left, *right;
};
// a utility function to create a new binary tree node
struct node *newnode(int item)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = item;
temp->left = temp->right = null;
return temp;
}
// recursive function to print right view of a binary tree.
void rightviewutil(struct node *root, int level, int *max_level)
{
// base case
if (root==null) return;
// if this is the last node of its level
if (*max_level < level)
{
printf("%d\t", root->data);
*max_level = level;
}
// recur for right subtree first, then left subtree
rightviewutil(root->right, level 1, max_level);
rightviewutil(root->left, level 1, max_level);
}
// a wrapper over rightviewutil()
void rightview(struct node *root)
{
int max_level = 0;
rightviewutil(root, 1, &max_level);
}
// driver program to test above functions
int main()
{
struct node *root = newnode(1);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(4);
root->left->right = newnode(5);
root->right->left = newnode(6);
root->right->right = newnode(7);
root->right->left->right = newnode(8);
rightview(root);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print right view of binary tree
// a binary tree node
class node {
int data;
node left, right;
node(int item) {
data = item;
left = right = null;
}
}
// class to access maximum level by reference
class max_level {
int max_level;
}
class binarytree {
node root;
max_level max = new max_level();
// recursive function to print right view of a binary tree.
void rightviewutil(node node, int level, max_level max_level) {
// base case
if (node == null)
return;
// if this is the last node of its level
if (max_level.max_level < level) {
system.out.print(node.data " ");
max_level.max_level = level;
}
// recur for right subtree first, then left subtree
rightviewutil(node.right, level 1, max_level);
rightviewutil(node.left, level 1, max_level);
}
void rightview()
{
rightview(root);
}
// a wrapper over rightviewutil()
void rightview(node node) {
rightviewutil(node, 1, max);
}
// driver program to test the above functions
public static void main(string args[]) {
binarytree tree = new binarytree();
tree.root = new node(1);
tree.root.left = new node(2);
tree.root.right = new node(3);
tree.root.left.left = new node(4);
tree.root.left.right = new node(5);
tree.root.right.left = new node(6);
tree.root.right.right = new node(7);
tree.root.right.left.right = new node(8);
tree.rightview();
}
}
// this code has been contributed by mayank jaiswal
计算机编程语言
# python program to print right view of binary tree
# a binary tree node
class node:
# a constructor to create a new binary tree node
def __init__(self, item):
self.data = item
self.left = none
self.right = none
# recursive function to print right view of binary tree
# used max_level as reference list ..only max_level[0]
# is helpful to us
def rightviewutil(root, level, max_level):
# base case
if root is none:
return
# if this is the last node of its level
if (max_level[0] < level):
print "%d " %(root.data),
max_level[0] = level
# recur for right subtree first, then left subtree
rightviewutil(root.right, level 1, max_level)
rightviewutil(root.left, level 1, max_level)
def rightview(root):
max_level = [0]
rightviewutil(root, 1, max_level)
# driver program to test above function
root = node(1)
root.left = node(2)
root.right = node(3)
root.left.left = node(4)
root.left.right = node(5)
root.right.left = node(6)
root.right.right = node(7)
root.right.left.right = node(8)
rightview(root)
# this code is contributed by nikhil kumar singh(nickzuck_007)
c
using system;
// c# program to print right view of binary tree
// a binary tree node
public class node
{
public int data;
public node left, right;
public node(int item)
{
data = item;
left = right = null;
}
}
// class to access maximum level by reference
public class max_level
{
public int max_level;
}
public class binarytree
{
public node root;
public max_level max = new max_level();
// recursive function to print right view of a binary tree.
public virtual void rightviewutil(node node, int level,
max_level max_level)
{
// base case
if (node == null)
{
return;
}
// if this is the last node of its level
if (max_level.max_level < level)
{
console.write(node.data " ");
max_level.max_level = level;
}
// recur for right subtree first, then left subtree
rightviewutil(node.right, level 1, max_level);
rightviewutil(node.left, level 1, max_level);
}
public virtual void rightview()
{
rightview(root);
}
// a wrapper over rightviewutil()
public virtual void rightview(node node)
{
rightviewutil(node, 1, max);
}
// driver program to test the above functions
public static void main(string[] args)
{
binarytree tree = new binarytree();
tree.root = new node(1);
tree.root.left = new node(2);
tree.root.right = new node(3);
tree.root.left.left = new node(4);
tree.root.left.right = new node(5);
tree.root.right.left = new node(6);
tree.root.right.right = new node(7);
tree.root.right.left.right = new node(8);
tree.rightview();
}
}
// this code is contributed by shrikant13
java 描述语言
output
1 3 7 8
对二叉树进行右视图时间复杂度:函数对树进行简单遍历，因此复杂度为 o(n)。
方法二:该方法讨论了基于解。如果我们仔细观察，会发现我们的主要任务是打印每一级最右边的节点。因此，我们将在树上进行级别顺序遍历，并在每个级别打印最后一个节点。下面是上述方法的实现:
c
// c program to print left view of
// binary tree
#include
using namespace std;
// a binary tree node
struct node {
int data;
struct node *left, *right;
};
// utility function to create a new tree node
node* newnode(int data)
{
node* temp = new node;
temp->data = data;
temp->left = temp->right = null;
return temp;
}
// function to print right view of
// binary tree
void printrightview(node* root)
{
if (root == null)
return;
queue q;
q.push(root);
while (!q.empty()) {
// get number of nodes for each level
int n = q.size();
// traverse all the nodes of the current level
while (n--) {
node* x = q.front();
q.pop();
// print the last node of each level
if (n == 0) {
cout << x->data << " ";
}
// if left child is not null push it into the
// queue
if (x->left)
q.push(x->left);
// if right child is not null push it into the
// queue
if (x->right)
q.push(x->right);
}
}
}
// driver code
int main()
{
// let's construct the tree as
// shown in example
node* root = newnode(1);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(4);
root->left->right = newnode(5);
root->right->left = newnode(6);
root->right->right = newnode(7);
root->right->left->right = newnode(8);
printrightview(root);
}
// this code is contributed by
// snehasish dhar
python 3
# python3 program to print right
# view of binary tree
from collections import deque
# a binary tree node
class node:
# a constructor to create a new
# binary tree node
def __init__(self, val):
self.data = val
self.left = none
self.right = none
# function to print right view of
# binary tree
def rightview(root):
if root is none:
return
q = deque()
q.append(root)
while q:
# get number of nodes for each level
n = len(q)
# traverse all the nodes of the
# current level
while n > 0:
n -= 1
# get the front node in the queue
node = q.popleft()
# print the last node of each level
if n == 0:
print(node.data, end = " ")
# if left child is not null push it
# into the queue
if node.left:
q.append(node.left)
# if right child is not null push
# it into the queue
if node.right:
q.append(node.right)
# driver code
# let's construct the tree as
# shown in example
root = node(1)
root.left = node(2)
root.right = node(3)
root.left.left = node(4)
root.left.right = node(5)
root.right.left = node(6)
root.right.right = node(7)
root.right.left.right = node(8)
rightview(root)
# this code is contributed by pulkit pansari
java 描述语言
java 语言(一种计算机语言，尤用于创建网站)
// java program to print right view of
// binary tree
import java.io.*;
import java.util.linkedlist;
import java.util.queue;
// a binary tree node
class node {
int data;
node left, right;
public node(int d)
{
data = d;
left = right = null;
}
}
class binarytree {
node root;
// function to print right view of
// binary tree
void rightview(node root)
{
if (root == null) {
return;
}
queue q = new linkedlist<>();
q.add(root);
while (!q.isempty()) {
// get number of nodes for each level
int n = q.size();
// traverse all the nodes of the current level
for (int i = 0; i < n; i ) {
node curr = q.peek();
q.remove();
// print the last node of each level
if (i == n - 1) {
system.out.print(curr.data);
system.out.print(" ");
}
// if left child is not null add it into
// the
// queue
if (curr.left != null) {
q.add(curr.left);
}
// if right child is not null add it into
// the
// queue
if (curr.right != null) {
q.add(curr.right);
}
}
}
}
// driver code
public static void main(string[] args)
{
// let's construct the tree as
// shown in example
binarytree tree = new binarytree();
tree.root = new node(1);
tree.root.left = new node(2);
tree.root.right = new node(3);
tree.root.left.left = new node(4);
tree.root.left.right = new node(5);
tree.root.right.left = new node(6);
tree.root.right.right = new node(7);
tree.root.right.left.right = new node(8);
tree.rightview(tree.root);
}
}
// this code is contributed by biswajit rajak
output
1 3 7 8
时间复杂度: o(n)，其中 n 为二叉树中的节点数。
本文由 biswajit rajak 供稿。如果你发现任何不正确的地方，请写评论，或者你想分享更多关于上面讨论的话题的信息
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
