给定一棵二叉树，打印每一层的角节点。最左边的节点和最右边的节点。 例如，下面的输出是 15, 10, 20, 8, 25 .
null
![图片[1]-打印二叉树最左边和最右边的节点-yiteyi-C++库](https://www.geeksforgeeks.org/wp-content/uploads/BinaryTree3-300x188.png)
一个简单的解决方案是使用本文讨论的方法进行两次遍历 打印左视图 和 右视图 . 我们能用一次遍历打印所有角点吗？ 这个想法是使用 水平顺序遍历 。每次我们将队列大小存储在变量n中时，该变量是该级别的节点数。对于每个级别，我们检查当前节点是否是第一个（即索引0处的节点）和最后一个索引处的节点（即索引n-1处的节点）。如果是其中一个，我们打印该节点的值。
// C/C++ program to print corner node at each level// of binary tree#include <bits/stdc++.h>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<Node*> 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;i<n;i++) { Node *temp = q.front(); q.pop(); //If it is leftmost corner value or rightmost corner value then print it if(i==0 || i==n-1) cout<<temp->key<<" "; //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 functionint 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<Node> q = new LinkedList<Node>(); // 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 |
Python3
# 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<Node> q = new Queue<Node>(); // 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是二叉树中的节点数。
本文由Utkarsh Choubey撰稿。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
