Dado un árbol binario, imprima los Nodes de las esquinas extremas de cada nivel pero en orden alternativo.
Ejemplo:
C++
/* C++ program to print nodes of extreme corners
of each level in alternate order */
#include <bits/stdc++.h>
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<Node*> 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<Node> q = new LinkedList<Node>();
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
# 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<Node> q = new Queue<Node>();
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
Javascript
<script>
// JavaScript program to print nodes of extreme corners
//of each level in alternate order
// A binary tree node has data, pointer to left child
//and a pointer to right child /
class Node
{
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
}
};
// Helper function that allocates a new node with the
//given data and null left and right pointers. /
function newNode(data)
{
var 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
function printExtremeNodes(root)
{
if (root == null)
return;
// Create a queue and enqueue left and right
// children of root
var q = [];
q.push(root);
// flag to indicate whether leftmost node or
// the rightmost node has to be printed
var flag = false;
while (q.length > 0)
{
// nodeCount indicates number of nodes
// at current level.
var nodeCount = q.length;
var n = nodeCount;
// Dequeue all nodes of current level
// and push all nodes of next level
while (n-->0)
{
var curr = q[0];
// push left child
if (curr.left != null)
q.push(curr.left);
// push right child
if (curr.right != null)
q.push(curr.right);
// Dequeue node
q.shift();
// if flag is true, print leftmost node
if (flag && n == nodeCount - 1)
document.write( curr.data + " ");
// if flag is false, print rightmost node
if (!flag && n == 0)
document.write( curr.data + " ");
}
// invert flag for next level
flag = !flag;
}
}
// Driver code
// Binary Tree of Height 4
var 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);
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA