Dado un árbol binario en el que los Nodes están numerados del 1 al n. Dado un Node y un entero positivo K. Tenemos que imprimir el ancestro Kth del Node dado en el árbol binario. Si no existe ningún ancestro de este tipo, imprima -1.
Por ejemplo, en el siguiente árbol binario, el segundo antepasado de 5 es 1. El tercer antepasado del Node 5 será -1.
C++
/* C++ program to calculate Kth ancestor of given node */
#include <bits/stdc++.h>
using namespace std;
// A Binary Tree Node
struct Node
{
int data;
struct Node *left, *right;
};
// temporary node to keep track of Node returned
// from previous recursive call during backtrack
Node* temp = NULL;
// recursive function to calculate Kth ancestor
Node* kthAncestorDFS(Node *root, int node , int &k)
{
// Base case
if (!root)
return NULL;
if (root->data == node||
(temp = kthAncestorDFS(root->left,node,k)) ||
(temp = kthAncestorDFS(root->right,node,k)))
{
if (k > 0)
k--;
else if (k == 0)
{
// print the kth ancestor
cout<<"Kth ancestor is: "<<root->data;
// return NULL to stop further backtracking
return NULL;
}
// return current node to previous call
return root;
}
}
// Utility function to create a new tree node
Node* newNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Driver program to test above functions
int main()
{
// Let us create binary tree shown in above diagram
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
int k = 2;
int node = 5;
// print kth ancestor of given node
Node* parent = kthAncestorDFS(root,node,k);
// check if parent is not NULL, it means
// there is no Kth ancestor of the node
if (parent)
cout << "-1";
return 0;
}
Java
// Java program to calculate Kth ancestor of given node
class Solution
{
// A Binary Tree Node
static class Node
{
int data;
Node left, right;
};
// temporary node to keep track of Node returned
// from previous recursive call during backtrack
static Node temp = null;
static int k;
// recursive function to calculate Kth ancestor
static Node kthAncestorDFS(Node root, int node )
{
// Base case
if (root == null)
return null;
if (root.data == node||
(temp = kthAncestorDFS(root.left,node)) != null ||
(temp = kthAncestorDFS(root.right,node)) != null)
{
if (k > 0)
k--;
else if (k == 0)
{
// print the kth ancestor
System.out.print("Kth ancestor is: "+root.data);
// return null to stop further backtracking
return null;
}
// return current node to previous call
return root;
}
return null;
}
// Utility function to create a new tree node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Driver code
public static void main(String args[])
{
// Let us create binary tree shown in above diagram
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
k = 2;
int node = 5;
// print kth ancestor of given node
Node parent = kthAncestorDFS(root,node);
// check if parent is not null, it means
// there is no Kth ancestor of the node
if (parent != null)
System.out.println("-1");
}
}
// This code is contributed by Arnab Kundu
Python3
""" Python3 program to calculate Kth
ancestor of given node """
# A Binary Tree Node
# Utility function to create a new tree node
class newNode:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# recursive function to calculate
# Kth ancestor
def kthAncestorDFS(root, node, k):
# Base case
if (not root):
return None
if (root.data == node or
(kthAncestorDFS(root.left, node, k)) or
(kthAncestorDFS(root.right, node, k))):
if (k[0] > 0):
k[0] -= 1
else if (k[0] == 0):
# print the kth ancestor
print("Kth ancestor is:", root.data)
# return None to stop further
# backtracking
return None
# return current node to previous call
return root
# Driver Code
if __name__ == '__main__':
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.left = newNode(4)
root.left.right = newNode(5)
k = [2]
node = 5
# print kth ancestor of given node
parent = kthAncestorDFS(root,node,k)
# check if parent is not None, it means
# there is no Kth ancestor of the node
if (parent):
print("-1")
# This code is contributed
# by SHUBHAMSINGH10
C#
// C# program to calculate Kth ancestor of given node
using System;
class GFG
{
// A Binary Tree Node
public class Node
{
public int data;
public Node left, right;
};
// temporary node to keep track of Node returned
// from previous recursive call during backtrack
static Node temp = null;
static int k;
// recursive function to calculate Kth ancestor
static Node kthAncestorDFS(Node root, int node )
{
// Base case
if (root == null)
return null;
if (root.data == node||
(temp = kthAncestorDFS(root.left,node)) != null ||
(temp = kthAncestorDFS(root.right,node)) != null)
{
if (k > 0)
k--;
else if (k == 0)
{
// print the kth ancestor
Console.Write("Kth ancestor is: "+root.data);
// return null to stop further backtracking
return null;
}
// return current node to previous call
return root;
}
return null;
}
// Utility function to create a new tree node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Driver code
public static void Main(String []args)
{
// Let us create binary tree shown in above diagram
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
k = 2;
int node = 5;
// print kth ancestor of given node
Node parent = kthAncestorDFS(root,node);
// check if parent is not null, it means
// there is no Kth ancestor of the node
if (parent != null)
Console.WriteLine("-1");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to calculate Kth
// ancestor of given node
// A Binary Tree Node
class Node
{
constructor()
{
this.data = 0;
this.left = null;
this.right = null;
}
};
// temporary node to keep track of Node returned
// from previous recursive call during backtrack
var temp = null;
var k = 0;
// recursive function to calculate Kth ancestor
function kthAncestorDFS(root, node )
{
// Base case
if (root == null)
return null;
if (root.data == node||
(temp = kthAncestorDFS(root.left,node)) != null ||
(temp = kthAncestorDFS(root.right,node)) != null)
{
if (k > 0)
k--;
else if (k == 0)
{
// print the kth ancestor
document.write("Kth ancestor is: "+root.data);
// return null to stop further backtracking
return null;
}
// return current node to previous call
return root;
}
return null;
}
// Utility function to create a new tree node
function newNode(data)
{
var temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Driver code
// Let us create binary tree shown in above diagram
var root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
k = 2;
var node = 5;
// print kth ancestor of given node
var parent = kthAncestorDFS(root,node);
// check if parent is not null, it means
// there is no Kth ancestor of the node
if (parent != null)
document.write("-1");
</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