原文:
给定一棵二叉树，打印每一层的角节点。最左边的节点和最右边的节点。 例如，以下输出为 15、10、20、8、25 。
一个简单的pg电子试玩链接的解决方案是使用针对和所讨论的方法进行两次遍历。 我们能用一次遍历打印所有的角节点吗？ 思路是使用。每次我们将队列的大小存储在变量 n 中，n 是该级别的节点数。对于每一级，我们检查当前节点是否是第一个(即索引 0 处的节点)和最后一个索引处的节点(即索引 n-1 处的节点)，如果是这两个节点中的任何一个，我们打印该节点的值。
c/c
// c/c program to print corner node at each level
// of binary tree
#include
using namespace std;
/* a binary tree node has key, pointer to left
child and a pointer to right child */
struct node
{
int key;
struct node* left, *right;
};
/* to create a newnode of tree and return pointer */
struct node* newnode(int key)
{
node* temp = new node;
temp->key = key;
temp->left = temp->right = null;
return (temp);
}
/* function to print corner node at each level */
void printcorner(node *root)
{
//if the root is null then simply return
if(root == null)
return;
//do level order traversal using a single queue
queue q;
q.push(root);
while(!q.empty())
{
//n denotes the size of the current level in the queue
int n = q.size();
for(int i =0;ikey<<" ";
//push the left and right children of the temp node
if(temp->left)
q.push(temp->left);
if(temp->right)
q.push(temp->right);
}
}
}
// driver program to test above function
int main ()
{
node *root = newnode(15);
root->left = newnode(10);
root->right = newnode(20);
root->left->left = newnode(8);
root->left->right = newnode(12);
root->right->left = newnode(16);
root->right->right = newnode(25);
printcorner(root);
return 0;
}
// this code is contributed by utkarsh choubey
java 语言(一种计算机语言，尤用于创建网站)
// java program to print corner node at each level in a binary tree
import java.util.*;
/* a binary tree node has key, pointer to left
child and a pointer to right child */
class node
{
int key;
node left, right;
public node(int key)
{
this.key = key;
left = right = null;
}
}
class binarytree
{
node root;
/* function to print corner node at each level */
void printcorner(node root)
{
// star node is for keeping track of levels
queue q = new linkedlist();
// pushing root node and star node
q.add(root);
// do level order traversal of binary tree
while (!q.isempty())
{
// n is the no of nodes in current level
int n = q.size();
for(int i = 0 ; i < n ; i ){
// dequeue the front node from the queue
node temp = q.peek();
q.poll();
//if it is leftmost corner value or rightmost corner value then print it
if(i==0 || i==n-1)
system.out.print(temp.key " ");
//push the left and right children of the temp node
if (temp.left != null)
q.add(temp.left);
if (temp.right != null)
q.add(temp.right);
}
}
}
// driver program to test above functions
public static void main(string[] args)
{
binarytree tree = new binarytree();
tree.root = new node(15);
tree.root.left = new node(10);
tree.root.right = new node(20);
tree.root.left.left = new node(8);
tree.root.left.right = new node(12);
tree.root.right.left = new node(16);
tree.root.right.right = new node(25);
tree.printcorner(tree.root);
}
}
// this code has been contributed by utkarsh choubey
python 3
# python3 program to print corner
# node at each level of binary tree
from collections import deque
# a binary tree node has key, pointer to left
# child and a pointer to right child
class node:
def __init__(self, key):
self.key = key
self.left = none
self.right = none
# function to print corner node at each level
def printcorner(root: node):
# if the root is null then simply return
if root == none:
return
# do level order traversal
# using a single queue
q = deque()
q.append(root)
while q:
# n denotes the size of the current
# level in the queue
n = len(q)
for i in range(n):
temp = q[0]
q.popleft()
# if it is leftmost corner value or
# rightmost corner value then print it
if i == 0 or i == n - 1:
print(temp.key, end = " ")
# push the left and right children
# of the temp node
if temp.left:
q.append(temp.left)
if temp.right:
q.append(temp.right)
# driver code
if __name__ == "__main__":
root = node(15)
root.left = node(10)
root.right = node(20)
root.left.left = node(8)
root.left.right = node(12)
root.right.left = node(16)
root.right.right = node(25)
printcorner(root)
# this code is contributed by sanjeev2552
c
// c# program to print corner node
// at each level in a binary tree
using system;
using system.collections.generic;
/* a binary tree node has key, pointer to left
child and a pointer to right child */
public class node
{
public int key;
public node left, right;
public node(int key)
{
this.key = key;
left = right = null;
}
}
public class binarytree
{
node root;
/* function to print corner node at each level */
void printcorner(node root)
{
// star node is for keeping track of levels
queue q = new queue();
// pushing root node and star node
q.enqueue(root);
// do level order traversal of binary tree
while (q.count != 0)
{
// n is the no of nodes in current level
int n = q.count;
for(int i = 0 ; i < n ; i ){
node temp = q.peek();
q.dequeue();
//if it is leftmost corner value or rightmost corner value then print it
if(i==0||i==n-1)
console.write(temp.key " ");
//push the left and right children of the temp node
if (temp.left != null)
q.enqueue(temp.left);
if (temp.right != null)
q.enqueue(temp.right);
}
}
}
// driver code
public static void main(string[] args)
{
binarytree tree = new binarytree();
tree.root = new node(15);
tree.root.left = new node(10);
tree.root.right = new node(20);
tree.root.left.left = new node(8);
tree.root.left.right = new node(12);
tree.root.right.left = new node(16);
tree.root.right.right = new node(25);
tree.printcorner(tree.root);
}
}
// this code is contributed by utkarsh choubey
输出:
15 10 20 8 25
时间复杂度: o(n)，其中 n 为二叉树中的节点数。
本文由乌卡什·乔贝供稿。如果你发现任何不正确的地方，或者你想分享更多关于上面讨论的话题的信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
