Considere líneas con una pendiente de -1 que atraviesan Nodes. Imprime todos los elementos diagonales en un árbol binario que pertenecen a la misma línea, dado un árbol binario.
Input : Root of below tree
Output : Diagonal Traversal of binary tree: 8 10 14 3 6 7 13 1 4 Observation : root and root->right values will be prioritized over all root->left values.
El plan es hacer uso de un mapa. En el mapa se utilizan diferentes distancias de pendiente como clave. El valor del mapa es un vector de Node (o array dinámica). Para guardar valores en el mapa, recorremos el árbol. Imprimimos el contenido del mapa una vez construido.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program for diagonal
// traversal of Binary Tree
#include <bits/stdc++.h>
using namespace std;
// Tree node
struct Node
{
int data;
Node *left, *right;
};
/* root - root of the binary tree
d - distance of current line from rightmost
-topmost slope.
diagonalPrint - multimap to store Diagonal
elements (Passed by Reference) */
void diagonalPrintUtil(Node* root, int d,
map<int, vector<int>> &diagonalPrint)
{
// Base case
if (!root)
return;
// Store all nodes of same
// line together as a vector
diagonalPrint[d].push_back(root->data);
// Increase the vertical
// distance if left child
diagonalPrintUtil(root->left,
d + 1, diagonalPrint);
// Vertical distance remains
// same for right child
diagonalPrintUtil(root->right,
d, diagonalPrint);
}
// Print diagonal traversal
// of given binary tree
void diagonalPrint(Node* root)
{
// create a map of vectors
// to store Diagonal elements
map<int, vector<int> > diagonalPrint;
diagonalPrintUtil(root, 0, diagonalPrint);
cout << "Diagonal Traversal of binary tree : \n";
for (auto it :diagonalPrint)
{
vector<int> v=it.second;
for(auto it:v)
cout<<it<<" ";
cout<<endl;
}
}
// Utility method to create a new node
Node* newNode(int data)
{
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
// Driver program
int main()
{
Node* root = newNode(8);
root->left = newNode(3);
root->right = newNode(10);
root->left->left = newNode(1);
root->left->right = newNode(6);
root->right->right = newNode(14);
root->right->right->left = newNode(13);
root->left->right->left = newNode(4);
root->left->right->right = newNode(7);
/* Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(9);
root->left->right = newNode(6);
root->right->left = newNode(4);
root->right->right = newNode(5);
root->right->left->right = newNode(7);
root->right->left->left = newNode(12);
root->left->right->left = newNode(11);
root->left->left->right = newNode(10);*/
diagonalPrint(root);
return 0;
}
Java
// Java program for diagonal
// traversal of Binary Tree
import java.util.TreeMap;
import java.util.Map.Entry;
import java.util.Vector;
public class DiagonalTraversalBTree
{
// Tree node
static class Node
{
int data;
Node left;
Node right;
//constructor
Node(int data)
{
this.data=data;
left = null;
right =null;
}
}
/* root - root of the binary tree
d - distance of current line from rightmost
-topmost slope.
diagonalPrint - HashMap to store Diagonal
elements (Passed by Reference) */
static void diagonalPrintUtil(Node root,int d,
TreeMap<Integer,Vector<Integer>> diagonalPrint)
{
// Base case
if (root == null)
return;
// get the list at the particular d value
Vector<Integer> k = diagonalPrint.get(d);
// k is null then create a
// vector and store the data
if (k == null)
{
k = new Vector<>();
k.add(root.data);
}
// k is not null then update the list
else
{
k.add(root.data);
}
// Store all nodes of same line
// together as a vector
diagonalPrint.put(d,k);
// Increase the vertical distance
// if left child
diagonalPrintUtil(root.left,
d + 1, diagonalPrint);
// Vertical distance remains
// same for right child
diagonalPrintUtil(root.right,
d, diagonalPrint);
}
// Print diagonal traversal
// of given binary tree
static void diagonalPrint(Node root)
{
// create a map of vectors
// to store Diagonal elements
TreeMap<Integer,Vector<Integer>>
diagonalPrint = new TreeMap<>();
diagonalPrintUtil(root, 0, diagonalPrint);
System.out.println("Diagonal Traversal of Binary Tree");
for (Entry<Integer, Vector<Integer>> entry :
diagonalPrint.entrySet())
{
System.out.println(entry.getValue());
}
}
// Driver program
public static void main(String[] args)
{
Node root = new Node(8);
root.left = new Node(3);
root.right = new Node(10);
root.left.left = new Node(1);
root.left.right = new Node(6);
root.right.right = new Node(14);
root.right.right.left = new Node(13);
root.left.right.left = new Node(4);
root.left.right.right = new Node(7);
diagonalPrint(root);
}
}
// This code is contributed by Sumit Ghosh
Python3
# Python program for diagonal
# traversal of Binary Tree
# A binary tree node
class Node:
# Constructor to create a
# new binary tree node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
""" root - root of the binary tree
d - distance of current line from rightmost
-topmost slope.
diagonalPrint - multimap to store Diagonal
elements (Passed by Reference) """
def diagonalPrintUtil(root, d, diagonalPrintMap):
# Base Case
if root is None:
return
# Store all nodes of same line
# together as a vector
try :
diagonalPrintMap[d].append(root.data)
except KeyError:
diagonalPrintMap[d] = [root.data]
# Increase the vertical distance
# if left child
diagonalPrintUtil(root.left,
d+1, diagonalPrintMap)
# Vertical distance remains
# same for right child
diagonalPrintUtil(root.right,
d, diagonalPrintMap)
# Print diagonal traversal of given binary tree
def diagonalPrint(root):
# Create a dict to store diagonal elements
diagonalPrintMap = dict()
# Find the diagonal traversal
diagonalPrintUtil(root, 0, diagonalPrintMap)
print ("Diagonal Traversal of binary tree : ")
for i in diagonalPrintMap:
for j in diagonalPrintMap[i]:
print (j,end=" ")
print()
# Driver Program
root = Node(8)
root.left = Node(3)
root.right = Node(10)
root.left.left = Node(1)
root.left.right = Node(6)
root.right.right = Node(14)
root.right.right.left = Node(13)
root.left.right.left = Node(4)
root.left.right.right = Node(7)
diagonalPrint(root)
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
Producción
Diagonal Traversal of binary tree : 8 10 14 3 6 7 13 1 4
Complejidad temporal: O( N logN )
Espacio auxiliar: O( N )
El problema idéntico se puede resolver con una cola y un método iterativo.
C++14
#include <bits/stdc++.h>
using namespace std;
// Tree node
struct Node {
int data;
Node *left, *right;
};
vector<int> diagonal(Node* root)
{
vector<int> diagonalVals;
if (!root)
return diagonalVals;
// The leftQueue will be a queue which will store all
// left pointers while traversing the tree, and will be
// utilized when at any point right pointer becomes NULL
queue<Node*> leftQueue;
Node* node = root;
while (node) {
// Add current node to output
diagonalVals.push_back(node->data);
// If left child available, add it to queue
if (node->left)
leftQueue.push(node->left);
// if right child, transfer the node to right
if (node->right)
node = node->right;
else {
// If left child Queue is not empty, utilize it
// to traverse further
if (!leftQueue.empty()) {
node = leftQueue.front();
leftQueue.pop();
}
else {
// All the right childs traversed and no
// left child left
node = NULL;
}
}
}
return diagonalVals;
}
// Utility method to create a new node
Node* newNode(int data)
{
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
// Driver program
int main()
{
Node* root = newNode(8);
root->left = newNode(3);
root->right = newNode(10);
root->left->left = newNode(1);
root->left->right = newNode(6);
root->right->right = newNode(14);
root->right->right->left = newNode(13);
root->left->right->left = newNode(4);
root->left->right->right = newNode(7);
/* Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(9);
root->left->right = newNode(6);
root->right->left = newNode(4);
root->right->right = newNode(5);
root->right->left->right = newNode(7);
root->right->left->left = newNode(12);
root->left->right->left = newNode(11);
root->left->left->right = newNode(10);*/
vector<int> diagonalValues = diagonal(root);
for (int i = 0; i < diagonalValues.size(); i++) {
cout << diagonalValues[i] << " ";
}
cout << endl;
return 0;
}
Java
// Java Code for above approach
import java.util.*;
// Tree node
class Node {
int data;
Node left, right;
};
class BinaryTree {
public static List<Integer> diagonal(Node root)
{
List<Integer> diagonalVals = new ArrayList<>();
if (root == null)
return diagonalVals;
// The leftQueue will be a queue which will store
// all left pointers while traversing the tree, and
// will be utilized when at any point right pointer
// becomes NULL
Queue<Node> leftQueue = new LinkedList<>();
Node node = root;
while (node != null) {
// Add current node to output
diagonalVals.add(node.data);
// If left child available, add it to queue
if (node.left != null)
leftQueue.add(node.left);
// if right child, transfer the node to right
if (node.right != null)
node = node.right;
else {
// If left child Queue is not empty, utilize
// it to traverse further
if (!leftQueue.isEmpty()) {
node = leftQueue.peek();
leftQueue.remove();
}
else {
// All the right childs traversed and no
// left child left
node = null;
}
}
}
return diagonalVals;
}
// Utility method to create a new node
public static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return node;
}
// Driver program
public static void main(String[] args)
{
Node root = newNode(8);
root.left = newNode(3);
root.right = newNode(10);
root.left.left = newNode(1);
root.left.right = newNode(6);
root.right.right = newNode(14);
root.right.right.left = newNode(13);
root.left.right.left = newNode(4);
root.left.right.right = newNode(7);
/* Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(9);
root->left->right = newNode(6);
root->right->left = newNode(4);
root->right->right = newNode(5);
root->right->left->right = newNode(7);
root->right->left->left = newNode(12);
root->left->right->left = newNode(11);
root->left->left->right = newNode(10);*/
List<Integer> diagonalValues = diagonal(root);
for (int i = 0; i < diagonalValues.size(); i++) {
System.out.print(diagonalValues.get(i) + " ");
}
System.out.println();
}
}
// This code is contributed by Tapesh(tapeshdua420)
Python3
from collections import deque # A binary tree node class Node: # Constructor to create a # new binary tree node def __init__(self, data): self.data = data self.left = None self.right = None def diagonal(root): out = [] node = root # queue to store left nodes left_q = deque() while node: # append data to output array out.append(node.data) # if left available add it to the queue if node.left: left_q.appendleft(node.left) # if right is available change the node if node.right: node = node.right else: # else pop the left_q if len(left_q) >= 1: node = left_q.pop() else: node = None return out # Driver Code root = Node(8) root.left = Node(3) root.right = Node(10) root.left.left = Node(1) root.left.right = Node(6) root.right.right = Node(14) root.right.right.left = Node(13) root.left.right.left = Node(4) root.left.right.right = Node(7) print(diagonal(root))
Producción
[8, 10, 14, 3, 6, 7, 13, 1, 4]
Complejidad temporal: O( N log N )
Espacio auxiliar: O(N)
Enfoque 2: uso de la cola:
cada Node contribuirá a la formación de la siguiente diagonal. Solo cuando la izquierda del elemento esté disponible, lo empujaremos a la cola. Procesaremos el Node y luego iremos a la derecha.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
Node *left, *right;
};
Node* newNode(int data)
{
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
vector <vector <int>> result;
void diagonalPrint(Node* root)
{
if(root == NULL)
return;
queue <Node*> q;
q.push(root);
while(!q.empty())
{
int size = q.size();
vector <int> answer;
while(size--)
{
Node* temp = q.front();
q.pop();
// traversing each component;
while(temp)
{
answer.push_back(temp->data);
if(temp->left)
q.push(temp->left);
temp = temp->right;
}
}
result.push_back(answer);
}
}
int main()
{
Node* root = newNode(8);
root->left = newNode(3);
root->right = newNode(10);
root->left->left = newNode(1);
root->left->right = newNode(6);
root->right->right = newNode(14);
root->right->right->left = newNode(13);
root->left->right->left = newNode(4);
root->left->right->right = newNode(7);
diagonalPrint(root);
for(int i=0 ; i<result.size() ; i++)
{
for(int j=0 ; j<result[i].size() ; j++)
cout<<result[i][j]<<" ";
cout<<endl;
}
return 0;
}
Java
import java.io.*;
import java.util.*;
class GFG{
// Tree node
static class Node
{
int data;
Node left;
Node right;
// Constructor
Node(int data)
{
this.data = data;
left = null;
right = null;
}
}
static class TNode
{
Node node;
int level;
public TNode(Node n, int l)
{
this.node = n;
this.level = l;
}
}
public static void diagonalPrint(Node root)
{
if (root == null)
{
return;
}
TreeMap<Integer,
List<Integer>> map = new TreeMap<Integer,
List<Integer>>();
Queue<TNode> q = new LinkedList<TNode>();
q.add(new TNode(root, 0));
while (!q.isEmpty())
{
TNode curr = q.poll();
map.putIfAbsent(curr.level, new ArrayList<>());
map.get(curr.level).add(curr.node.data);
if (curr.node.left != null)
{
q.add(new TNode(curr.node.left,
curr.level + 1));
}
if (curr.node.right != null)
{
q.add(new TNode(curr.node.right,
curr.level));
}
}
for(Map.Entry<Integer, List<Integer>>
entry : map.entrySet())
{
int k = entry.getKey();
List<Integer> l = map.get(k);
int size = l.size();
for(int i = 0; i < l.size(); i++)
{
System.out.print(l.get(i));
System.out.print(" ");
}
System.out.println("");
}
return;
}
// Driver code
public static void main(String[] args)
{
Node root = new Node(8);
root.left = new Node(3);
root.right = new Node(10);
root.left.left = new Node(1);
root.left.right = new Node(6);
root.right.right = new Node(14);
root.right.right.left = new Node(13);
root.left.right.left = new Node(4);
root.left.right.right = new Node(7);
diagonalPrint(root);
}
}
// This code is contributed by abhinaygupta98
Python3
# Python Program to print diagonal traversal using queue # Tree Node class Node: def __init__(self, x): self.data = x self.left = None self.right = None def diagonalPrint(root): if root is None: return q = [] q.append(root) while len(q) > 0: size = len(q) answer = [] while size > 0: temp = q[0] q.pop(0) # traversing each component; while temp is not None: answer.append(temp.data) if temp.left is not None: q.append(temp.left) temp = temp.right size -= 1 result.append(answer) if __name__ == '__main__': root = Node(8) root.left = Node(3) root.right = Node(10) root.left.left = Node(1) root.left.right = Node(6) root.right.right = Node(14) root.right.right.left = Node(13) root.left.right.left = Node(4) root.left.right.right = Node(7) result = [] diagonalPrint(root) for i in range(len(result)): for j in range(len(result[i])): print(result[i][j], end=" ") print() # This code is contributed by Tapesh(tapeshdua420)
C#
// C# implementation of above approach
using System;
using System.Collections.Generic;
public class Node {
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = null;
right = null;
}
}
class GFG {
static List<List<int> > result = new List<List<int> >();
static void printLevelOrder(Node root)
{
if (root == null)
return;
Queue<Node> q = new Queue<Node>();
q.Enqueue(root);
while (q.Count != 0) {
int size = q.Count;
List<int> answer = new List<int>();
while (size-- != 0) {
Node temp = q.Dequeue();
// traversing each component;
while (temp != null) {
answer.Add(temp.data);
if (temp.left != null)
q.Enqueue(temp.left);
temp = temp.right;
}
}
result.Add(answer);
}
}
// Driver code
public static void Main()
{
Node root = new Node(8);
root.left = new Node(3);
root.right = new Node(10);
root.left.left = new Node(1);
root.left.right = new Node(6);
root.right.right = new Node(14);
root.right.right.left = new Node(13);
root.left.right.left = new Node(4);
root.left.right.right = new Node(7);
printLevelOrder(root);
for (int i = 0; i < result.Count; i++) {
for (int j = 0; j < result[i].Count; j++) {
Console.Write(result[i][j]);
Console.Write(" ");
}
Console.WriteLine();
}
}
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)
Producción
8 10 14 3 6 7 13 1 4
Complejidad de tiempo: O(N), porque estamos visitando los Nodes una vez.
Espacio Auxiliar: O(N), porque estamos usando una cola.
Este artículo es una contribución de Aditya Goel . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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