Dado un árbol binario y un valor K . La tarea es imprimir el k-ésimo Node en el recorrido diagonal del árbol binario. Si no existe tal Node, imprima -1.
Ejemplos:
Input : 8 / \ 3 10 / / \ 1 6 14 / \ / 4 7 13 k = 5 Output : 6 Diagonal Traversal of the above tree is: 8 10 14 3 6 7 13 1 4 Input : 1 / \ 2 3 / \ 4 5 k = 7 Output : -1
Enfoque: La idea es realizar el recorrido diagonal del árbol binario hasta que se visiten K Nodes en el recorrido diagonal. Mientras recorre cada Node visitado, disminuya el valor de la variable K y devuelva el Node actual cuando el valor de K sea cero. Si el recorrido diagonal no contiene al menos K Nodes, devuelve -1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print kth node // in the diagonal traversal of a binary tree #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 Node* newNode(int data) { Node* node = new Node(); node->data = data; node->left = node->right = NULL; return (node); } // Iterative function to print kth node // in diagonal traversal of binary tree int diagonalPrint(Node* root, int k) { // Base cases if (root == NULL || k == 0) return -1; int ans = -1; queue<Node*> q; // Push root node q.push(root); // Push delimiter NULL q.push(NULL); while (!q.empty()) { Node* temp = q.front(); q.pop(); if (temp == NULL) { if (q.empty()) { // If kth node exists then return // the answer if (k == 0) return ans; // If kth node doesnt exists // then break from the while loop else break; } q.push(NULL); } else { while (temp) { // If the required kth node // has been found then return the answer if (k == 0) return ans; k--; // Update the value of variable ans // each time ans = temp->data; if (temp->left) q.push(temp->left); temp = temp->right; } } } // If kth node doesnt exists then // return -1 return -1; } // Driver Code 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); int k = 9; cout << diagonalPrint(root, k); return 0; }
Java
// Java program to print kth node // in the diagonal traversal of a binary tree 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 static Node newNode(int data) { Node node = new Node(); node.data = data; node.left = node.right = null; return (node); } // Iterative function to print kth node // in diagonal traversal of binary tree static int diagonalPrint(Node root, int k) { // Base cases if (root == null || k == 0) return -1; int ans = -1; Queue<Node> q = new LinkedList<Node>(); // add root node q.add(root); // add delimiter null q.add(null); while (q.size() > 0) { Node temp = q.peek(); q.remove(); if (temp == null) { if (q.size() == 0) { // If kth node exists then return // the answer if (k == 0) return ans; // If kth node doesnt exists // then break from the while loop else break; } q.add(null); } else { while (temp != null) { // If the required kth node // has been found then return the answer if (k == 0) return ans; k--; // Update the value of variable ans // each time ans = temp.data; if (temp.left!=null) q.add(temp.left); temp = temp.right; } } } // If kth node doesnt exists then // return -1 return -1; } // Driver Code 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); int k = 9; System.out.println( diagonalPrint(root, k)); } } // This code is contributed by Arnab Kundu
Python3
# Python program to print kth node # in the diagonal traversal of a binary tree # Linked List node class Node: def __init__(self, data): self.data = data self.left = None self.right = None # Helper function that allocates a new node def newNode(data) : node = Node(0) node.data = data node.left = node.right = None return (node) # Iterative function to print kth node # in diagonal traversal of binary tree def diagonalPrint( root, k) : # Base cases if (root == None or k == 0) : return -1 ans = -1 q = [] # append root node q.append(root) # append delimiter None q.append(None) while (len(q) > 0): temp = q[0] q.pop(0) if (temp == None): if (len(q) == 0) : # If kth node exists then return # the answer if (k == 0) : return ans # If kth node doesnt exists # then break from the while loop else: break q.append(None) else : while (temp != None): # If the required kth node # has been found then return the answer if (k == 0) : return ans k = k - 1 # Update the value of variable ans # each time ans = temp.data if (temp.left != None): q.append(temp.left) temp = temp.right # If kth node doesnt exists then # return -1 return -1 # Driver Code 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) k = 9 print( diagonalPrint(root, k)) # This code is contributed by Arnab Kundu
C#
// C# program to print kth node // in the diagonal traversal of a binary tree 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 static Node newNode(int data) { Node node = new Node(); node.data = data; node.left = node.right = null; return (node); } // Iterative function to print kth node // in diagonal traversal of binary tree static int diagonalPrint(Node root, int k) { // Base cases if (root == null || k == 0) return -1; int ans = -1; Queue<Node> q = new Queue<Node>(); // Enqueue root node q.Enqueue(root); // Enqueue delimiter null q.Enqueue(null); while (q.Count > 0) { Node temp = q.Peek(); q.Dequeue(); if (temp == null) { if (q.Count == 0) { // If kth node exists then return // the answer if (k == 0) return ans; // If kth node doesnt exists // then break from the while loop else break; } q.Enqueue(null); } else { while (temp != null) { // If the required kth node // has been found then return the answer if (k == 0) return ans; k--; // Update the value of variable ans // each time ans = temp.data; if (temp.left!=null) q.Enqueue(temp.left); temp = temp.right; } } } // If kth node doesnt exists then // return -1 return -1; } // Driver Code 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); int k = 9; Console.WriteLine( diagonalPrint(root, k)); } } /* This code is contributed by PrinciRaj1992 */
Javascript
<script> // JavaScript program to print kth node // in the diagonal traversal of a binary tree // 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 function newNode(data) { var node = new Node(); node.data = data; node.left = node.right = null; return (node); } // Iterative function to print kth node // in diagonal traversal of binary tree function diagonalPrint(root, k) { // Base cases if (root == null || k == 0) return -1; var ans = -1; var q = []; // push root node q.push(root); // push delimiter null q.push(null); while (q.length > 0) { var temp = q[0]; q.shift(); if (temp == null) { if (q.length == 0) { // If kth node exists then return // the answer if (k == 0) return ans; // If kth node doesnt exists // then break from the while loop else break; } q.push(null); } else { while (temp != null) { // If the required kth node // has been found then return the answer if (k == 0) return ans; k--; // Update the value of variable ans // each time ans = temp.data; if (temp.left!=null) q.push(temp.left); temp = temp.right; } } } // If kth node doesnt exists then // return -1 return -1; } // Driver Code var 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); var k = 9; document.write( diagonalPrint(root, k)); </script>
4
Complejidad temporal : O(N), donde N es el número total de Nodes en el árbol binario.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Sakshi_Srivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA