原文:
给定一个二叉树，打印它的右下视图。二叉树的右下方视图是从右下方访问树时可见的一组节点，返回从右向左排序的节点值。 在右下视图中，从右下侧以 45 度角查看树时，只有几个节点可见，其余节点隐藏在后面。 例:
input :
1
/ \
2 3
\ \
5 4
output : [4, 5]
visible nodes from the bottom right direction are 4 and 5
input :
1
/ \
2 3
/ /
4 5
\
6
output: [3, 6, 4]
进场:
- 这个问题可以用简单的递归遍历来解决。
- 通过向所有递归调用传递参数来跟踪节点的级别。以 45%的角度考虑一棵树的高度(如一个例子中所解释的)，所以每当我们向左移动时，它的高度就会增加一。
- 其思想是跟踪最大级别，并以在访问左子树之前访问右子树的方式遍历树。
- 级别超过最大级别的节点，打印该节点，因为这是其级别中的最后一个节点(在左子树之前遍历右子树)。
以下是上述方法的实现:
c
// c program to print bottom
// right view of binary tree
#include
using namespace std;
// a binary tree node
struct node
{
int data;
node *left, *right;
node(int item)
{
data = item;
left = right = null;
}
};
// class to access maximum level
// by reference
struct _max_level
{
int _max_level;
};
node *root;
_max_level *_max = new _max_level();
// recursive function to print bottom
// right view of a binary tree
void bottomrightviewutil(node* node, int level,
_max_level *_max_level)
{
// base case
if (node == null)
return;
// recur for right subtree first
bottomrightviewutil(node->right,
level, _max_level);
// if this is the last node of its level
if (_max_level->_max_level < level)
{
cout << node->data << " ";
_max_level->_max_level = level;
}
// recur for left subtree
// with increased level
bottomrightviewutil(node->left,
level 1, _max_level);
}
// a wrapper over bottomrightviewutil()
void bottomrightview(node *node)
{
bottomrightviewutil(node, 1, _max);
}
void bottomrightview()
{
bottomrightview(root);
}
// driver code
int main()
{
root = new node(1);
root->left = new node(2);
root->right = new node(3);
root->left->left = new node(4);
root->right->left = new node(5);
root->right->left->right = new node(6);
bottomrightview();
}
// this code is contributed by arnab kundu
java 语言(一种计算机语言，尤用于创建网站)
// java program to print bottom
// 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 bottom
// right view of a binary tree.
void bottomrightviewutil(node node, int level,
max_level max_level)
{
// base case
if (node == null)
return;
// recur for right subtree first
bottomrightviewutil(node.right,
level, max_level);
// 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 left subtree with increased level
bottomrightviewutil(node.left,
level 1, max_level);
}
void bottomrightview()
{
bottomrightview(root);
}
// a wrapper over bottomrightviewutil()
void bottomrightview(node node)
{
bottomrightviewutil(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.right.left = new node(5);
tree.root.right.left.right = new node(6);
tree.bottomrightview();
}
}
python 3
# python3 program to print bottom
# right view of binary tree
# a binary tree node
class node:
# construct to create a newnode
def __init__(self, item):
self.data = item
self.left = none
self.right = none
maxlevel = [0]
# recursive function to print bottom
# right view of a binary tree.
def bottomrightviewutil(node, level, maxlevel):
# base case
if (node == none):
return
# recur for right subtree first
bottomrightviewutil(node.right, level,
maxlevel)
# if this is the last node of its level
if (maxlevel[0] < level):
print(node.data, end = " ")
maxlevel[0] = level
# recur for left subtree with increased level
bottomrightviewutil(node.left, level 1,
maxlevel)
# a wrapper over bottomrightviewutil()
def bottomrightview(node):
bottomrightviewutil(node, 1, maxlevel)
# driver code
root = node(1)
root.left = node(2)
root.right = node(3)
root.left.left = node(4)
root.right.left = node(5)
root.right.left.right = node(6)
bottomrightview(root)
# this code is contributed by shubhamsingh10
c
// c# program to print bottom
// right view of binary tree
using system;
// a binary tree node
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
class max_level
{
public int max_level;
}
class gfg
{
node root;
max_level max = new max_level();
// recursive function to print bottom
// right view of a binary tree.
void bottomrightviewutil(node node, int level,
max_level max_level)
{
// base case
if (node == null)
return;
// recur for right subtree first
bottomrightviewutil(node.right,
level, max_level);
// 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 left subtree with increased level
bottomrightviewutil(node.left,
level 1, max_level);
}
void bottomrightview()
{
bottomrightview(root);
}
// a wrapper over bottomrightviewutil()
void bottomrightview(node node)
{
bottomrightviewutil(node, 1, max);
}
// driver code
public static void main(string []args)
{
gfg tree = new gfg();
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.right.left = new node(5);
tree.root.right.left.right = new node(6);
tree.bottomrightview();
}
}
// this code is contributed by princi singh
java 描述语言
output:
3 6 4
时间复杂度: o(n)，其中 n 为二叉树的节点数。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
