K-й узел в диагональном обходе двоичного дерева
Опубликовано: 23 Января, 2022
Дано двоичное дерево и значение K. Задача - вывести k-й узел диагонального обхода двоичного дерева. Если такой узел не существует, выведите -1.
Примеры:
Вход :
8
/
3 10
/ /
1 6 14
/ /
4 7 13
k = 5
Выход: 6
Диагональный обход дерева выше:
8 10 14
3 6 7 13
1 4
Вход :
1
/
2 3
/
4 5
к = 7
Выход: -1
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход: идея состоит в том, чтобы выполнить диагональный обход двоичного дерева до тех пор, пока при диагональном обходе не будут посещены K узлов. При обходе для каждого посещенного узла уменьшите значение переменной K и верните текущий узел, когда значение K станет равным нулю. Если диагональный обход не содержит по крайней мере K узлов, верните -1.
Below is the implementation of the above approach:
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 leftchild and a pointer to right child struct Node { int data; Node *left, *right;}; // Helper function that allocates a new nodeNode* newNode(int data){ Node* node = (Node*)malloc(sizeof(Node)); node->data = data; node->left = node->right = NULL; return (node);} // Iterative function to print kth node// in diagonal traversal of binary treeint 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 Codeint 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 childstatic 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 |
Python
# 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); РЕКОМЕНДУЕМЫЕ СТАТЬИ |