给定一棵二叉树，其中节点的编号从1到n。给定一个节点和一个正整数K。我们必须在二叉树中打印给定节点的第K个祖先。如果不存在任何这样的祖先，那么打印-1。 例如，在下面给定的二叉树中，节点4和5的第二个祖先是1。节点4的第三个祖先将是-1。
null
![图片[1]-二叉树中节点的第K个祖先-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/uploads/tree122-1.gif)
这样做的想法是首先遍历二叉树，并将每个节点的祖先存储在一个大小为n的数组中。例如，假设该数组是anecestor[n]。然后在索引i处，祖先[i]将存储第i个节点的祖先。因此，第i个节点的第二个祖先将是祖先[祖先[i]，依此类推。我们将使用这个想法来计算给定节点的第k个祖先。我们可以使用 水平顺序遍历 来填充这些祖先。
下面是上述想法的实现。
C++
/* C++ program to calculate Kth ancestor of given node */ #include <iostream> #include <queue> using namespace std; // A Binary Tree Node struct Node { int data; struct Node *left, *right; }; // function to generate array of ancestors void generateArray(Node *root, int ancestors[]) { // There will be no ancestor of root node ancestors[root->data] = -1; // level order traversal to // generate 1st ancestor queue<Node*> q; q.push(root); while (!q.empty()) { Node* temp = q.front(); q.pop(); if (temp->left) { ancestors[temp->left->data] = temp->data; q.push(temp->left); } if (temp->right) { ancestors[temp->right->data] = temp->data; q.push(temp->right); } } } // function to calculate Kth ancestor int kthAncestor(Node *root, int n, int k, int node) { // create array to store 1st ancestors int ancestors[n+1] = {0}; // generate first ancestor array generateArray(root,ancestors); // variable to track record of number of // ancestors visited int count = 0; while (node!=-1) { node = ancestors[node]; count++; if (count==k) break ; } // print Kth ancestor return node; } // 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 cout<<kthAncestor(root,5,k,node); return 0; } |
JAVA
/* Java program to calculate Kth ancestor of given node */ import java.util.*; class GfG { // A Binary Tree Node static class Node { int data; Node left, right; } // function to generate array of ancestors static void generateArray(Node root, int ancestors[]) { // There will be no ancestor of root node ancestors[root.data] = - 1 ; // level order traversal to // generate 1st ancestor Queue<Node> q = new LinkedList<Node> (); q.add(root); while (!q.isEmpty()) { Node temp = q.peek(); q.remove(); if (temp.left != null ) { ancestors[temp.left.data] = temp.data; q.add(temp.left); } if (temp.right != null ) { ancestors[temp.right.data] = temp.data; q.add(temp.right); } } } // function to calculate Kth ancestor static int kthAncestor(Node root, int n, int k, int node) { // create array to store 1st ancestors int ancestors[] = new int [n + 1 ]; // generate first ancestor array generateArray(root,ancestors); // variable to track record of number of // ancestors visited int count = 0 ; while (node!=- 1 ) { node = ancestors[node]; count++; if (count==k) break ; } // print Kth ancestor return node; } // Utility function to create a new tree node static Node newNode( int data) { Node temp = new Node(); temp.data = data; temp.left = null ; temp.right = null ; return temp; } // Driver program to test above functions 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 ); int k = 2 ; int node = 5 ; // print kth ancestor of given node System.out.println(kthAncestor(root, 5 ,k,node)); } } |
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 newNode def __init__( self , data): self .data = data self .left = None self .right = None # function to generate array of ancestors def generateArray(root, ancestors): # There will be no ancestor of root node ancestors[root.data] = - 1 # level order traversal to # generate 1st ancestor q = [] q.append(root) while ( len (q)): temp = q[ 0 ] q.pop( 0 ) if (temp.left): ancestors[temp.left.data] = temp.data q.append(temp.left) if (temp.right): ancestors[temp.right.data] = temp.data q.append(temp.right) # function to calculate Kth ancestor def kthAncestor(root, n, k, node): # create array to store 1st ancestors ancestors = [ 0 ] * (n + 1 ) # generate first ancestor array generateArray(root,ancestors) # variable to track record of number # of ancestors visited count = 0 while (node ! = - 1 ) : node = ancestors[node] count + = 1 if (count = = k): break # prKth ancestor return node # Driver Code if __name__ = = '__main__' : # Let us create binary tree shown # in above diagram 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 # prkth ancestor of given node print (kthAncestor(root, 5 , k, node)) # This code is contributed by # SHUBHAMSINGH10 |
C#
/* C# program to calculate Kth ancestor of given node */ using System; using System.Collections.Generic; class GfG { // A Binary Tree Node public class Node { public int data; public Node left, right; } // function to generate array of ancestors static void generateArray(Node root, int []ancestors) { // There will be no ancestor of root node ancestors[root.data] = -1; // level order traversal to // generate 1st ancestor LinkedList<Node> q = new LinkedList<Node> (); q.AddLast(root); while (q.Count != 0) { Node temp = q.First.Value; q.RemoveFirst(); if (temp.left != null ) { ancestors[temp.left.data] = temp.data; q.AddLast(temp.left); } if (temp.right != null ) { ancestors[temp.right.data] = temp.data; q.AddLast(temp.right); } } } // function to calculate Kth ancestor static int kthAncestor(Node root, int n, int k, int node) { // create array to store 1st ancestors int []ancestors = new int [n + 1]; // generate first ancestor array generateArray(root,ancestors); // variable to track record of number of // ancestors visited int count = 0; while (node != -1) { node = ancestors[node]; count++; if (count == k) break ; } // print Kth ancestor return node; } // Utility function to create a new tree node static Node newNode( int data) { Node temp = new Node(); temp.data = data; temp.left = null ; temp.right = null ; return temp; } // Driver program to test above functions 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); int k = 2; int node = 5; // print kth ancestor of given node Console.WriteLine(kthAncestor(root,5,k,node)); } } // This code has been 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 ; } } // function to generate array of ancestors function generateArray(root, ancestors) { // There will be no ancestor of root node ancestors[root.data] = -1; // level order traversal to // generate 1st ancestor var q = []; q.push(root); while (q.length != 0) { var temp = q[0]; q.shift(); if (temp.left != null ) { ancestors[temp.left.data] = temp.data; q.push(temp.left); } if (temp.right != null ) { ancestors[temp.right.data] = temp.data; q.push(temp.right); } } } // function to calculate Kth ancestor function kthAncestor(root, n, k, node) { // create array to store 1st ancestors var ancestors = Array(n+1).fill(0); // generate first ancestor array generateArray(root,ancestors); // variable to track record of number of // ancestors visited var count = 0; while (node != -1) { node = ancestors[node]; count++; if (count == k) break ; } // print Kth ancestor return node; } // Utility function to create a new tree node function newNode(data) { var temp = new Node(); temp.data = data; temp.left = null ; temp.right = null ; return temp; } // Driver program to test above functions // 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); var k = 2; var node = 5; // print kth ancestor of given node document.write(kthAncestor(root,5,k,node)); </script> |
输出：
1
时间复杂性 ：O（n） 辅助空间 ：O（n）
方法2： 在这个方法中，首先我们将得到一个元素，它的祖先必须被搜索，从那个节点开始，我们将一个接一个地减少计数，直到我们到达那个祖先节点。 例如——
考虑下面给出的树：
(1)
/
(4) (2)
/
(3) (7) (6)
(8)
然后检查k=0，如果是，则返回该元素作为祖先，否则向上爬一层并减少k（k=k-1）。 最初k=2 我们先搜索8然后， 在8=>检查是否（k==0）但k=2，因此k=k-1=>k=2-1=1，并在7时爬升一级 在7=>检查是否（k==0）但k=1，因此k=k-1=>k=1-1=0，并在4处爬升一级 在4=>检查是否（k==0）是k=0将此节点作为祖先返回。
C++14
// C++ program for finding // kth ancestor of a particular node #include<bits/stdc++.h> using namespace std; // Structure for a node struct node{ int data; struct node *left, *right; node( int x) { data = x; left = right = NULL; } }; // Program to find kth ancestor bool ancestor( struct node* root, int item, int &k) { if (root == NULL) return false ; // Element whose ancestor is to be searched if (root->data == item) { //reduce count by 1 k = k-1; return true ; } else { // Checking in left side bool flag = ancestor(root->left,item,k); if (flag) { if (k == 0) { // If count = 0 i.e. element is found cout<< "[" <<root->data<< "] " ; return false ; } // if count !=0 i.e. this is not the // ancestor we are searching for // so decrement count k = k-1; return true ; } // Similarly Checking in right side bool flag2 = ancestor(root->right,item,k); if (flag2) { if (k == 0) { cout<< "[" <<root->data<< "] " ; return false ; } k = k-1; return true ; } } } // Driver Code int main() { struct node* root = new node(1); root->left = new node(4); root->left->right = new node(7); root->left->left = new node(3); root->left->right->left = new node(8); root->right = new node(2); root->right->right = new node(6); int item,k; item = 3; k = 1; int loc = k; bool flag = ancestor(root,item,k); if (flag) cout<< "Ancestor doesn't exist" ; else cout<< "is the " <<loc<< "th ancestor of [" << item<< "]" <<endl; return 0; } // This code is contributed by Sanjeev Yadav. |
JAVA
// Java program for finding // kth ancestor of a particular node import java.io.*; class Node { int data; Node left, right; Node( int x) { this .data = x; this .left = this .right = null ; } } class GFG{ static int k = 1 ; static boolean ancestor(Node root, int item) { if (root == null ) return false ; // Element whose ancestor is to be searched if (root.data == item) { // Reduce count by 1 k = k- 1 ; return true ; } else { // Checking in left side boolean flag = ancestor(root.left, item); if (flag) { if (k == 0 ) { // If count = 0 i.e. element is found System.out.print( "[" + root.data + "] " ); return false ; } // If count !=0 i.e. this is not the // ancestor we are searching for // so decrement count k = k - 1 ; return true ; } // Similarly Checking in right side boolean flag2 = ancestor(root.right, item); if (flag2) { if (k == 0 ) { System.out.print( "[" + root.data + "] " ); return false ; } k = k - 1 ; return true ; } } return false ; } // Driver code public static void main(String[] args) { Node root = new Node( 1 ); root.left = new Node( 4 ); root.left.right = new Node( 7 ); root.left.left = new Node( 3 ); root.left.right.left = new Node( 8 ); root.right = new Node( 2 ); root.right.right = new Node( 6 ); int item = 3 ; int loc = k; boolean flag = ancestor(root, item); if (flag) System.out.println( "Ancestor doesn't exist" ); else System.out.println( "is the " + (loc) + "th ancestor of [" + (item) + "]" ); } } // This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 program for finding # kth ancestor of a particular node # Structure for a node class node: def __init__( self , data): self .left = None self .right = None self .data = data # Program to find kth ancestor def ancestor(root, item): global k if (root = = None ): return False # Element whose ancestor is # to be searched if (root.data = = item): # Reduce count by 1 k = k - 1 return True else : # Checking in left side flag = ancestor(root.left, item); if (flag): if (k = = 0 ): # If count = 0 i.e. element is found print ( "[" + str (root.data) + "]" , end = ' ' ) return False # If count !=0 i.e. this is not the # ancestor we are searching for # so decrement count k = k - 1 return True # Similarly Checking in right side flag2 = ancestor(root.right, item) if (flag2): if (k = = 0 ): print ( "[" + str (root.data) + "]" ) return False k = k - 1 return True # Driver code if __name__ = = "__main__" : root = node( 1 ) root.left = node( 4 ) root.left.right = node( 7 ) root.left.left = node( 3 ) root.left.right.left = node( 8 ) root.right = node( 2 ) root.right.right = node( 6 ) item = 3 k = 1 loc = k flag = ancestor(root, item) if (flag): print ( "Ancestor doesn't exist" ) else : print ( "is the " + str (loc) + "th ancestor of [" + str (item) + "]" ) # This code is contributed by rutvik_56 |
C#
// C# program for finding // kth ancestor of a particular node using System; // Structure for a node public class Node { public int data; public Node left, right; public Node( int x) { this .data = x; this .left = this .right = null ; } } class GFG{ static int k = 1; // Program to find kth ancestor static bool ancestor(Node root, int item) { if (root == null ) return false ; // Element whose ancestor is // to be searched if (root.data == item) { // Reduce count by 1 k = k - 1; return true ; } else { // Checking in left side bool flag = ancestor(root.left, item); if (flag) { if (k == 0) { // If count = 0 i.e. element is found Console.Write( "[" + root.data + "] " ); return false ; } // If count !=0 i.e. this is not the // ancestor we are searching for // so decrement count k = k - 1; return true ; } // Similarly Checking in right side bool flag2 = ancestor(root.right, item); if (flag2) { if (k == 0) { Console.Write( "[" + root.data + "] " ); return false ; } k = k - 1; return true ; } } return false ; } // Driver code static public void Main() { Node root = new Node(1); root.left = new Node(4); root.left.right = new Node(7); root.left.left = new Node(3); root.left.right.left = new Node(8); root.right = new Node(2); root.right.right = new Node(6); int item = 3; int loc = k; bool flag = ancestor(root, item); if (flag) Console.WriteLine( "Ancestor doesn't exist" ); else Console.WriteLine( "is the " + (loc) + "th ancestor of [" + (item) + "]" ); } } // This code is contributed by patel2127 |
Javascript
<script> class Node { constructor(x) { this .data=x; this .left = this .right = null ; } } function ancestor(root, item) { if (root == null ) { return false ; } if (root.data == item) { k = k - 1; return true ; } else { let flag = ancestor(root.left, item); if (flag) { if (k == 0) { document.write( "[" + (root.data) + "] " ); return false ; } k = k - 1; return true ; } let flag2 = ancestor(root.right, item); if (flag2) { if (k == 0) { document.write( "[" + (root.data) + "] " ); return false ; } k = k - 1; return true ; } } } let root = new Node(1) root.left = new Node(4) root.left.right = new Node(7) root.left.left = new Node(3) root.left.right.left = new Node(8) root.right = new Node(2) root.right.right = new Node(6) let item = 3 let k = 1 let loc = k let flag = ancestor(root, item) if (flag) document.write( "Ancestor doesn't exist" ) else document.write( "is the " + (loc) + "th ancestor of [" + (item) + "]" ) // This code is contributed by rag2127 </script> |
输出
[4] is the 1th ancestor of [3]
本文由 严酷的阿加瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
