原文:
给定一个二叉树，打印它的左视图。二叉树的左视图是从左侧访问树时可见的一组节点。
示例:
input :
1
/ \
2 3
/ \ \
4 5 6
output : 1 2 4
input :
1
/ \
2 3
\
4
\
5
\
6
output :1 2 4 5 6
方法 1(使用递归) 左视图包含所有节点，这些节点是其级别中的第一个节点。简单的解决方法就是做 并打印每一级中的第一个节点。
问题也可以通过简单的递归遍历来解决。我们可以通过向所有递归调用传递一个参数来跟踪节点的级别。这个想法也是为了跟踪最大水平。每当我们看到一个节点的级别超过目前为止的最大级别，我们就打印该节点，因为这是其级别中的第一个节点(注意，我们在右子树之前遍历左子树)。
以下是上述想法的实现-
c
// c program to print left 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
// left view of a binary tree.
void leftviewutil(struct node *root,
int level, int *max_level)
{
// base case
if (root == null) return;
// if this is the first node of its level
if (*max_level < level)
{
cout << root->data << " ";
*max_level = level;
}
// recur for left subtree first,
// then right subtree
leftviewutil(root->left, level 1, max_level);
leftviewutil(root->right, level 1, max_level);
}
// a wrapper over leftviewutil()
void leftview(struct node *root)
{
int max_level = 0;
leftviewutil(root, 1, &max_level);
}
// driver code
int main()
{
node* root = newnode(10);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(7);
root->left->right = newnode(8);
root->right->right = newnode(15);
root->right->left = newnode(12);
root->right->right->left = newnode(14);
leftview(root);
return 0;
}
c
// c program to print left 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 left view of a binary tree.
void leftviewutil(struct node* root, int level,
int* max_level)
{
// base case
if (root == null)
return;
// if this is the first node of its level
if (*max_level < level) {
printf("%d\t", root->data);
*max_level = level;
}
// recur for left and right subtrees
leftviewutil(root->left, level 1, max_level);
leftviewutil(root->right, level 1, max_level);
}
// a wrapper over leftviewutil()
void leftview(struct node* root)
{
int max_level = 0;
leftviewutil(root, 1, &max_level);
}
// driver code
int main()
{
struct node* root = newnode(12);
root->left = newnode(10);
root->right = newnode(30);
root->right->left = newnode(25);
root->right->right = newnode(40);
leftview(root);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print left view of binary tree
/* class containing left and right child of current
node and key value*/
class node {
int data;
node left, right;
public node(int item)
{
data = item;
left = right = null;
}
}
/* class to print the left view */
class binarytree {
node root;
static int max_level = 0;
// recursive function to print left view
void leftviewutil(node node, int level)
{
// base case
if (node == null)
return;
// if this is the first node of its level
if (max_level < level) {
system.out.print(" " node.data);
max_level = level;
}
// recur for left and right subtrees
leftviewutil(node.left, level 1);
leftviewutil(node.right, level 1);
}
// a wrapper over leftviewutil()
void leftview()
{
leftviewutil(root, 1);
}
/* testing for example nodes */
public static void main(string args[])
{
/* creating a binary tree and entering the nodes */
binarytree tree = new binarytree();
tree.root = new node(12);
tree.root.left = new node(10);
tree.root.right = new node(30);
tree.root.right.left = new node(25);
tree.root.right.right = new node(40);
tree.leftview();
}
}
计算机编程语言
# python program to print left view of binary tree
# a binary tree node
class node:
# constructor to create a new node
def __init__(self, data):
self.data = data
self.left = none
self.right = none
# recursive function print left view of a binary tree
def leftviewutil(root, level, max_level):
# base case
if root is none:
return
# if this is the first node of its level
if (max_level[0] < level):
print "% d\t" %(root.data),
max_level[0] = level
# recur for left and right subtree
leftviewutil(root.left, level 1, max_level)
leftviewutil(root.right, level 1, max_level)
# a wrapper over leftviewutil()
def leftview(root):
max_level = [0]
leftviewutil(root, 1, max_level)
# driver program to test above function
root = node(12)
root.left = node(10)
root.right = node(20)
root.right.left = node(25)
root.right.right = node(40)
leftview(root)
# this code is contributed by nikhil kumar singh(nickzuck_007)
c
using system;
// c# program to print left view of binary tree
/* class containing left and right child of current
node and key value*/
public class node {
public int data;
public node left, right;
public node(int item)
{
data = item;
left = right = null;
}
}
/* class to print the left view */
public class binarytree {
public node root;
public static int max_level = 0;
// recursive function to print left view
public virtual void leftviewutil(node node, int level)
{
// base case
if (node == null) {
return;
}
// if this is the first node of its level
if (max_level < level) {
console.write(" " node.data);
max_level = level;
}
// recur for left and right subtrees
leftviewutil(node.left, level 1);
leftviewutil(node.right, level 1);
}
// a wrapper over leftviewutil()
public virtual void leftview()
{
leftviewutil(root, 1);
}
/* testing for example nodes */
public static void main(string[] args)
{
/* creating a binary tree and entering the nodes */
binarytree tree = new binarytree();
tree.root = new node(12);
tree.root.left = new node(10);
tree.root.right = new node(30);
tree.root.right.left = new node(25);
tree.root.right.right = new node(40);
tree.leftview();
}
}
// this code is contributed by shrikant13
java 描述语言
output
10 2 7 14
时间复杂度:函数对树做简单遍历，所以复杂度为 o(n)。 辅助空间: o(n)，由于递归调用时的栈空间。
方法-2 (使用队列):
在该方法中，讨论了基于水平顺序遍历的pg电子试玩链接的解决方案。如果我们仔细观察，会发现我们的主要任务是打印每一级最左边的节点。因此，我们将在树上进行级别顺序遍历，并在每个级别打印最左边的节点。下面是上述方法的实现:
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 left view of
// binary tree
void printleftview(node* root)
{
if (!root)
return;
queue q;
q.push(root);
while (!q.empty())
{
// number of nodes at current level
int n = q.size();
// traverse all nodes of current level
for(int i = 1; i <= n; i )
{
node* temp = q.front();
q.pop();
// print the left most element
// at the level
if (i == 1)
cout<data<<" ";
// add left node to queue
if (temp->left != null)
q.push(temp->left);
// add right node to queue
if (temp->right != null)
q.push(temp->right);
}
}
}
// driver code
int main()
{
// let's construct the tree as
// shown in example
node* root = newnode(10);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(7);
root->left->right = newnode(8);
root->right->right = newnode(15);
root->right->left = newnode(12);
root->right->right->left = newnode(14);
printleftview(root);
}
// this code is contributed by
// manne sreecharan
java 语言(一种计算机语言，尤用于创建网站)
// java program to print left view of binary
// tree
import java.util.*;
public class printrightview {
// binary tree node
private static class node {
int data;
node left, right;
public node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// function to print left view of binary tree
private static void printleftview(node root)
{
if (root == null)
return;
queue queue = new linkedlist<>();
queue.add(root);
while (!queue.isempty()) {
// number of nodes at current level
int n = queue.size();
// traverse all nodes of current level
for (int i = 1; i <= n; i ) {
node temp = queue.poll();
// print the left most element at
// the level
if (i == 1)
system.out.print(temp.data " ");
// add left node to queue
if (temp.left != null)
queue.add(temp.left);
// add right node to queue
if (temp.right != null)
queue.add(temp.right);
}
}
}
// driver code
public static void main(string[] args)
{
// construct binary tree as shown in
// above diagram
node root = new node(10);
root.left = new node(2);
root.right = new node(3);
root.left.left = new node(7);
root.left.right = new node(8);
root.right.right = new node(15);
root.right.left = new node(12);
root.right.right.left = new node(14);
printleftview(root);
}
}
// this code is contributed by
// manne sreecharan
计算机编程语言
# python3 program to print left view of
# binary tree
# binary tree node
""" utility that allocates a newnode
with the given key """
class newnode:
# construct to create a newnode
def __init__(self, key):
self.data = key
self.left = none
self.right = none
self.hd = 0
# function to print left view of
# binary tree
def printleftview(root):
if (not root):
return
q = []
q.append(root)
while (len(q)):
# number of nodes at current level
n = len(q)
# traverse all nodes of current level
for i in range(1, n 1):
temp = q[0]
q.pop(0)
# print the left most element
# at the level
if (i == 1):
print(temp.data, end=" ")
# add left node to queue
if (temp.left != none):
q.append(temp.left)
# add right node to queue
if (temp.right != none):
q.append(temp.right)
# driver code
if __name__ == '__main__':
root = newnode(10)
root.left = newnode(2)
root.right = newnode(3)
root.left.left = newnode(7)
root.left.right = newnode(8)
root.right.right = newnode(15)
root.right.left = newnode(12)
root.right.right.left = newnode(14)
printleftview(root)
# this code is contributed by
# manne sreecharan
c
// c# program to print left view
// of binary tree
using system;
using system.collections.generic;
public class printrightview {
// binary tree node
private class node {
public int data;
public node left, right;
public node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// function to print left view of binary tree
private static void printrightview(node root)
{
if (root == null)
return;
queue queue = new queue();
queue.enqueue(root);
while (queue.count != 0) {
// number of nodes at current level
int n = queue.count;
// traverse all nodes of current level
for (int i = 1; i <= n; i ) {
node temp = queue.dequeue();
// print the left most element at
// the level
if (i == n)
console.write(temp.data " ");
// add left node to queue
if (temp.left != null)
queue.enqueue(temp.left);
// add right node to queue
if (temp.right != null)
queue.enqueue(temp.right);
}
}
}
// driver code
public static void main(string[] args)
{
// construct binary tree as shown in
// above diagram
node root = new node(10);
root.left = new node(2);
root.right = new node(3);
root.left.left = new node(7);
root.left.right = new node(8);
root.right.right = new node(15);
root.right.left = new node(12);
root.right.right.left = new node(14);
printrightview(root);
}
}
// this code is contributed manne sreecharan
output
10 2 7 14
时间复杂度: o(n)，其中 n 为二叉树中的节点数。
方法 3:
使用队列和空指针来标记每个级别的第一个元素
我们在第一个元素中插入一个空指针，当到达该空指针时，我们将 bool 标记为 true，并将下一个元素作为左视图元素
c
#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;
}
vector leftview(node *root)
{
// your code here
vectorans;
if(!root)
{
return ans;
}
queueq;
q.push(root);
q.push(null);
bool ok=true;
while(!q.empty())
{
auto it=q.front();
q.pop();
if(it==null)
{
if(ok==false)
{
ok=true;
}
if(q.size()==0)
{
break;
}
else
{
q.push(null);
}
}
else
{
if(ok)
{
ans.push_back(it->data);
ok=false;
}
if(it->left)
{
q.push(it->left);
}
if(it->right)
{
q.push(it->right);
}
}
}
return ans;
}
int main()
{
node* root = newnode(10);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(7);
root->left->right = newnode(8);
root->right->right = newnode(15);
root->right->left = newnode(12);
root->right->right->left = newnode(14);
vector vec = leftview(root);
for(int x : vec)
cout<
时间复杂度:o(n)，其中 n 是节点总数
本文由 ramsai chinthamani，manne sreecharan 供稿，如发现任何不正确的地方，或想分享更多关于上述话题的信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
