给定一棵二叉树和一个节点，打印给定节点的所有近亲。请注意，不应打印兄弟姐妹。 例子：
null
Input : root of below tree 1 / 2 3 / / 4 5 6 7 and pointer to a node say 5.Output : 6, 7
首先使用本文讨论的方法找到给定节点的级别 在这里 .一旦找到级别，我们就可以使用讨论的方法打印给定级别上的所有节点 在这里 .唯一需要注意的是，兄弟姐妹不应该被打印出来。为了处理这个问题，我们将打印功能更改为首先检查同级节点，并且仅当它不是同级节点时才打印节点。 下面是上述想法的实现。
C++
// C++ program to print cousins of a node #include <bits/stdc++.h> using namespace std; // A Binary Tree Node struct Node { int data; Node *left, *right; }; // A utility function to create a new // Binary Tree Node Node *newNode( int item) { Node *temp = new Node; temp->data = item; temp->left = temp->right = NULL; return temp; } /* It returns level of the node if it is present in tree, otherwise returns 0.*/ int getLevel(Node *root, Node *node, int level) { // base cases if (root == NULL) return 0; if (root == node) return level; // If node is present in left subtree int downlevel = getLevel(root->left, node, level + 1); if (downlevel != 0) return downlevel; // If node is not present in left subtree return getLevel(root->right, node, level + 1); } /* Print nodes at a given level such that sibling of node is not printed if it exists */ void printGivenLevel(Node* root, Node *node, int level) { // Base cases if (root == NULL || level < 2) return ; // If current node is parent of a node // with given level if (level == 2) { if (root->left == node || root->right == node) return ; if (root->left) cout << root->left->data << " " ; if (root->right) cout << root->right->data; } // Recur for left and right subtrees else if (level > 2) { printGivenLevel(root->left, node, level - 1); printGivenLevel(root->right, node, level - 1); } } // This function prints cousins of a given node void printCousins(Node *root, Node *node) { // Get level of given node int level = getLevel(root, node, 1); // Print nodes of given level. printGivenLevel(root, node, level); } // Driver Code int main() { Node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->left->right->right = newNode(15); root->right->left = newNode(6); root->right->right = newNode(7); root->right->left->right = newNode(8); printCousins(root, root->left->right); return 0; } // This code is contributed // by Akanksha Rai |
C
// C program to print cousins of a node #include <stdio.h> #include <stdlib.h> // A Binary Tree Node struct Node { int data; Node *left, *right; }; // A utility function to create a new Binary // Tree Node Node *newNode( int item) { Node *temp = new Node; temp->data = item; temp->left = temp->right = NULL; return temp; } /* It returns level of the node if it is present in tree, otherwise returns 0.*/ int getLevel(Node *root, Node *node, int level) { // base cases if (root == NULL) return 0; if (root == node) return level; // If node is present in left subtree int downlevel = getLevel(root->left, node, level+1); if (downlevel != 0) return downlevel; // If node is not present in left subtree return getLevel(root->right, node, level+1); } /* Print nodes at a given level such that sibling of node is not printed if it exists */ void printGivenLevel(Node* root, Node *node, int level) { // Base cases if (root == NULL || level < 2) return ; // If current node is parent of a node with // given level if (level == 2) { if (root->left == node || root->right == node) return ; if (root->left) printf ( "%d " , root->left->data); if (root->right) printf ( "%d " , root->right->data); } // Recur for left and right subtrees else if (level > 2) { printGivenLevel(root->left, node, level-1); printGivenLevel(root->right, node, level-1); } } // This function prints cousins of a given node void printCousins(Node *root, Node *node) { // Get level of given node int level = getLevel(root, node, 1); // Print nodes of given level. printGivenLevel(root, node, level); } // Driver Program to test above functions int main() { Node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->left->right->right = newNode(15); root->right->left = newNode(6); root->right->right = newNode(7); root->right->left->right = newNode(8); printCousins(root, root->left->right); return 0; } |
JAVA
// Java program to print cousins of a node class GfG { // A Binary Tree Node static class Node { int data; Node left, right; } // A utility function to create a new Binary // Tree Node static Node newNode( int item) { Node temp = new Node(); temp.data = item; temp.left = null ; temp.right = null ; return temp; } /* It returns level of the node if it is present in tree, otherwise returns 0.*/ static int getLevel(Node root, Node node, int level) { // base cases if (root == null ) return 0 ; if (root == node) return level; // If node is present in left subtree int downlevel = getLevel(root.left, node, level+ 1 ); if (downlevel != 0 ) return downlevel; // If node is not present in left subtree return getLevel(root.right, node, level+ 1 ); } /* Print nodes at a given level such that sibling of node is not printed if it exists */ static void printGivenLevel(Node root, Node node, int level) { // Base cases if (root == null || level < 2 ) return ; // If current node is parent of a node with // given level if (level == 2 ) { if (root.left == node || root.right == node) return ; if (root.left != null ) System.out.print(root.left.data + " " ); if (root.right != null ) System.out.print(root.right.data + " " ); } // Recur for left and right subtrees else if (level > 2 ) { printGivenLevel(root.left, node, level- 1 ); printGivenLevel(root.right, node, level- 1 ); } } // This function prints cousins of a given node static void printCousins(Node root, Node node) { // Get level of given node int level = getLevel(root, node, 1 ); // Print nodes of given level. printGivenLevel(root, node, level); } // Driver Program to test above functions public static void main(String[] args) { Node root = newNode( 1 ); root.left = newNode( 2 ); root.right = newNode( 3 ); root.left.left = newNode( 4 ); root.left.right = newNode( 5 ); root.left.right.right = newNode( 15 ); root.right.left = newNode( 6 ); root.right.right = newNode( 7 ); root.right.left.right = newNode( 8 ); printCousins(root, root.left.right); } } |
Python3
# Python3 program to print cousins of a node # A utility function to create a new # Binary Tree Node class newNode: def __init__( self , item): self .data = item self .left = self .right = None # It returns level of the node if it is # present in tree, otherwise returns 0. def getLevel(root, node, level): # base cases if (root = = None ): return 0 if (root = = node): return level # If node is present in left subtree downlevel = getLevel(root.left, node, level + 1 ) if (downlevel ! = 0 ): return downlevel # If node is not present in left subtree return getLevel(root.right, node, level + 1 ) # Print nodes at a given level such that # sibling of node is not printed if # it exists def printGivenLevel(root, node, level): # Base cases if (root = = None or level < 2 ): return # If current node is parent of a # node with given level if (level = = 2 ): if (root.left = = node or root.right = = node): return if (root.left): print (root.left.data, end = " " ) if (root.right): print (root.right.data, end = " " ) # Recur for left and right subtrees else if (level > 2 ): printGivenLevel(root.left, node, level - 1 ) printGivenLevel(root.right, node, level - 1 ) # This function prints cousins of a given node def printCousins(root, node): # Get level of given node level = getLevel(root, node, 1 ) # Print nodes of given level. printGivenLevel(root, node, level) # 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 ) root.left.right.right = newNode( 15 ) root.right.left = newNode( 6 ) root.right.right = newNode( 7 ) root.right.left.right = newNode( 8 ) printCousins(root, root.left.right) # This code is contributed by PranchalK |
C#
// C# program to print cousins of a node using System; public class GfG { // A Binary Tree Node class Node { public int data; public Node left, right; } // A utility function to create // a new Binary Tree Node static Node newNode( int item) { Node temp = new Node(); temp.data = item; temp.left = null ; temp.right = null ; return temp; } /* It returns level of the node if it is present in tree, otherwise returns 0.*/ static int getLevel(Node root, Node node, int level) { // base cases if (root == null ) return 0; if (root == node) return level; // If node is present in left subtree int downlevel = getLevel(root.left, node, level + 1); if (downlevel != 0) return downlevel; // If node is not present in left subtree return getLevel(root.right, node, level + 1); } /* Print nodes at a given level such that sibling of node is not printed if it exists */ static void printGivenLevel(Node root, Node node, int level) { // Base cases if (root == null || level < 2) return ; // If current node is parent of a node with // given level if (level == 2) { if (root.left == node || root.right == node) return ; if (root.left != null ) Console.Write(root.left.data + " " ); if (root.right != null ) Console.Write(root.right.data + " " ); } // Recur for left and right subtrees else if (level > 2) { printGivenLevel(root.left, node, level - 1); printGivenLevel(root.right, node, level - 1); } } // This function prints cousins of a given node static void printCousins(Node root, Node node) { // Get level of given node int level = getLevel(root, node, 1); // Print nodes of given level. printGivenLevel(root, node, level); } // Driver code public static void Main(String[] args) { Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.left.right.right = newNode(15); root.right.left = newNode(6); root.right.right = newNode(7); root.right.left.right = newNode(8); printCousins(root, root.left.right); } } // This code is contributed Rajput-Ji |
Javascript
<script> // JavaScript program to print cousins of a node // A Binary Tree Node class Node { constructor() { this .data=0; this .left= null ; this .right = null ; } } // A utility function to create // a new Binary Tree Node function newNode(item) { var temp = new Node(); temp.data = item; temp.left = null ; temp.right = null ; return temp; } /* It returns level of the node if it is present in tree, otherwise returns 0.*/ function getLevel(root, node, level) { // base cases if (root == null ) return 0; if (root == node) return level; // If node is present in left subtree var downlevel = getLevel(root.left, node, level + 1); if (downlevel != 0) return downlevel; // If node is not present in left subtree return getLevel(root.right, node, level + 1); } /* Print nodes at a given level such that sibling of node is not printed if it exists */ function printGivenLevel(root, node, level) { // Base cases if (root == null || level < 2) return ; // If current node is parent of a node with // given level if (level == 2) { if (root.left == node || root.right == node) return ; if (root.left != null ) document.write(root.left.data + " " ); if (root.right != null ) document.write(root.right.data + " " ); } // Recur for left and right subtrees else if (level > 2) { printGivenLevel(root.left, node, level - 1); printGivenLevel(root.right, node, level - 1); } } // This function prints cousins of a given node function printCousins(root, node) { // Get level of given node var level = getLevel(root, node, 1); // Print nodes of given level. printGivenLevel(root, node, level); } // Driver code var root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.left.right.right = newNode(15); root.right.left = newNode(6); root.right.right = newNode(7); root.right.left.right = newNode(8); printCousins(root, root.left.right); </script> |
输出：
6 7
时间复杂性： O（n） 我们能用单次遍历解决这个问题吗？请参考下面的文章 在二叉树中打印给定节点的近亲|单次遍历 本文由 希瓦姆·古普塔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
