原文:
给定一棵二叉树，以交替的顺序打印每一级的极端角落的节点。 示例:
对于上面的树， 输出可以是 1 2 7 8 31 –打印一级最右节点 –打印二级最左节点 –打印三级最右节点 –打印四级最左节点 –打印五级最右节点 或 1 3 4 15 16 –打印一级最左节点 –打印二级最右节点 –打印 第三级 最左边节点–打印第四级 最右边节点–打印第五级 最左边节点
这个想法是逐层遍历树。对于每个级别，我们计算其中的节点数，并根据布尔标志的值打印其最左边或最右边的节点。我们将当前级别的所有节点出队，将下一级别的所有节点入队，并在切换级别时反转布尔标志的值。 以下是上述思路的实现–
c
/* c program to print nodes of extreme corners
of each level in alternate order */
#include
using namespace std;
/* a binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
node *left, *right;
};
/* helper function that allocates a new node with the
given data and null left and right pointers. */
node* newnode(int data)
{
node* node = new node;
node->data = data;
node->right = node->left = null;
return node;
}
/* function to print nodes of extreme corners
of each level in alternate order */
void printextremenodes(node* root)
{
if (root == null)
return;
// create a queue and enqueue left and right
// children of root
queue q;
q.push(root);
// flag to indicate whether leftmost node or
// the rightmost node has to be printed
bool flag = false;
while (!q.empty())
{
// nodecount indicates number of nodes
// at current level.
int nodecount = q.size();
int n = nodecount;
// dequeue all nodes of current level
// and enqueue all nodes of next level
while (n--)
{
node* curr = q.front();
// enqueue left child
if (curr->left)
q.push(curr->left);
// enqueue right child
if (curr->right)
q.push(curr->right);
// dequeue node
q.pop();
// if flag is true, print leftmost node
if (flag && n == nodecount - 1)
cout << curr->data << " ";
// if flag is false, print rightmost node
if (!flag && n == 0)
cout << curr->data << " ";
}
// invert flag for next level
flag = !flag;
}
}
/* driver program to test above functions */
int main()
{
// binary tree of height 4
node* root = newnode(1);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(4);
root->left->right = newnode(5);
root->right->right = newnode(7);
root->left->left->left = newnode(8);
root->left->left->right = newnode(9);
root->left->right->left = newnode(10);
root->left->right->right = newnode(11);
root->right->right->left = newnode(14);
root->right->right->right = newnode(15);
root->left->left->left->left = newnode(16);
root->left->left->left->right = newnode(17);
root->right->right->right->right = newnode(31);
printextremenodes(root);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print nodes of extreme corners
//of each level in alternate order
import java.util.*;
class gfg
{
// a binary tree node has data, pointer to left child
//and a pointer to right child /
static class node
{
int data;
node left, right;
};
// helper function that allocates a new node with the
//given data and null left and right pointers. /
static node newnode(int data)
{
node node = new node();
node.data = data;
node.right = node.left = null;
return node;
}
// function to print nodes of extreme corners
//of each level in alternate order
static void printextremenodes(node root)
{
if (root == null)
return;
// create a queue and enqueue left and right
// children of root
queue q = new linkedlist();
q.add(root);
// flag to indicate whether leftmost node or
// the rightmost node has to be printed
boolean flag = false;
while (q.size()>0)
{
// nodecount indicates number of nodes
// at current level.
int nodecount = q.size();
int n = nodecount;
// dequeue all nodes of current level
// and enqueue all nodes of next level
while (n-->0)
{
node curr = q.peek();
// enqueue left child
if (curr.left!=null)
q.add(curr.left);
// enqueue right child
if (curr.right!=null)
q.add(curr.right);
// dequeue node
q.remove();
// if flag is true, print leftmost node
if (flag && n == nodecount - 1)
system.out.print( curr.data " ");
// if flag is false, print rightmost node
if (!flag && n == 0)
system.out.print( curr.data " ");
}
// invert flag for next level
flag = !flag;
}
}
// driver code
public static void main(string args[])
{
// binary tree of height 4
node root = newnode(1);
root.left = newnode(2);
root.right = newnode(3);
root.left.left = newnode(4);
root.left.right = newnode(5);
root.right.right = newnode(7);
root.left.left.left = newnode(8);
root.left.left.right = newnode(9);
root.left.right.left = newnode(10);
root.left.right.right = newnode(11);
root.right.right.left = newnode(14);
root.right.right.right = newnode(15);
root.left.left.left.left = newnode(16);
root.left.left.left.right = newnode(17);
root.right.right.right.right = newnode(31);
printextremenodes(root);
}
}
// this code is contributed by arnab kundu
计算机编程语言
# python program to print nodes of extreme corners
# of each level in alternate order
# utility class to create a node
class node:
def __init__(self, key):
self.data = key
self.left = self.right = none
# utility function to create a tree node
def newnode( data):
temp = node(0)
temp.data = data
temp.left = temp.right = none
return temp
# function to print nodes of extreme corners
# of each level in alternate order
def printextremenodes( root):
if (root == none):
return
# create a queue and enqueue left and right
# children of root
q = []
q.append(root)
# flag to indicate whether leftmost node or
# the rightmost node has to be printed
flag = false
while (len(q) > 0):
# nodecount indicates number of nodes
# at current level.
nodecount = len(q)
n = nodecount
# dequeue all nodes of current level
# and enqueue all nodes of next level
while (n > 0):
n = n - 1
curr = q[0]
# enqueue left child
if (curr.left != none):
q.append(curr.left)
# enqueue right child
if (curr.right != none):
q.append(curr.right)
# dequeue node
q.pop(0)
# if flag is true, print leftmost node
if (flag and n == nodecount - 1):
print( curr.data , end=" ")
# if flag is false, print rightmost node
if (not flag and n == 0):
print( curr.data ,end= " ")
# invert flag for next level
flag = not flag
# driver program to test above functions
# binary tree of height 4
root = newnode(1)
root.left = newnode(2)
root.right = newnode(3)
root.left.left = newnode(4)
root.left.right = newnode(5)
root.right.right = newnode(7)
root.left.left.left = newnode(8)
root.left.left.right = newnode(9)
root.left.right.left = newnode(10)
root.left.right.right = newnode(11)
root.right.right.left = newnode(14)
root.right.right.right = newnode(15)
root.left.left.left.left = newnode(16)
root.left.left.left.right = newnode(17)
root.right.right.right.right = newnode(31)
printextremenodes(root)
# this code is contributed by arnab kundu
c
// c# program to print nodes of extreme corners
//of each level in alternate order
using system;
using system.collections.generic;
class gfg
{
// a binary tree node has data, pointer to left child
//and a pointer to right child /
public class node
{
public int data;
public node left, right;
};
// helper function that allocates a new node with the
//given data and null left and right pointers. /
static node newnode(int data)
{
node node = new node();
node.data = data;
node.right = node.left = null;
return node;
}
// function to print nodes of extreme corners
//of each level in alternate order
static void printextremenodes(node root)
{
if (root == null)
return;
// create a queue and enqueue left and right
// children of root
queue q = new queue();
q.enqueue(root);
// flag to indicate whether leftmost node or
// the rightmost node has to be printed
boolean flag = false;
while (q.count > 0)
{
// nodecount indicates number of nodes
// at current level.
int nodecount = q.count;
int n = nodecount;
// dequeue all nodes of current level
// and enqueue all nodes of next level
while (n-->0)
{
node curr = q.peek();
// enqueue left child
if (curr.left != null)
q.enqueue(curr.left);
// enqueue right child
if (curr.right != null)
q.enqueue(curr.right);
// dequeue node
q.dequeue();
// if flag is true, print leftmost node
if (flag && n == nodecount - 1)
console.write( curr.data " ");
// if flag is false, print rightmost node
if (!flag && n == 0)
console.write( curr.data " ");
}
// invert flag for next level
flag = !flag;
}
}
// driver code
public static void main(string []args)
{
// binary tree of height 4
node root = newnode(1);
root.left = newnode(2);
root.right = newnode(3);
root.left.left = newnode(4);
root.left.right = newnode(5);
root.right.right = newnode(7);
root.left.left.left = newnode(8);
root.left.left.right = newnode(9);
root.left.right.left = newnode(10);
root.left.right.right = newnode(11);
root.right.right.left = newnode(14);
root.right.right.right = newnode(15);
root.left.left.left.left = newnode(16);
root.left.left.left.right = newnode(17);
root.right.right.right.right = newnode(31);
printextremenodes(root);
}
}
// this code is contributed by rajput-ji
java 描述语言
输出:
1 2 7 8 31
上述解的时间复杂度为 o(n)，其中 n 为给定二叉树中的节点总数。
练习–从下到上交替打印每一级的最角节点。 本文由阿迪蒂亚·戈尔供稿。如果你喜欢 geeksforgeeks 并想投稿，你也可以使用写一篇文章或者把你的文章邮寄到 review-team@geeksforgeeks.org。看到你的文章出现在极客博客pg电子试玩链接主页上，帮助其他极客。 如果发现有不正确的地方，或者想分享更多关于上述话题的信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
