给定一棵树的根和一个整数k。打印距离根k的所有节点。 例如，在下面的树中，4、5和8与根的距离为2。
null
1 / 2 3 / / 4 5 8
这个问题可以用递归来解决。感谢埃尔霍提出的解决方案。
C++
#include<bits/stdc++.h> using namespace std; /* A binary tree node has data, pointer to left child and a pointer to right child */ class node { public : int data; node* left; node* right; /* Constructor that allocates a new node with the given data and NULL left and right pointers. */ node( int data) { this ->data = data; this ->left = NULL; this ->right = NULL; } }; void printKDistant(node *root , int k) { if (root == NULL|| k < 0 ) return ; if ( k == 0 ) { cout << root->data << " " ; return ; } printKDistant( root->left, k - 1 ) ; printKDistant( root->right, k - 1 ) ; } /* Driver code*/ int main() { /* Constructed binary tree is 1 / 2 3 / / 4 5 8 */ node *root = new node(1); root->left = new node(2); root->right = new node(3); root->left->left = new node(4); root->left->right = new node(5); root->right->left = new node(8); printKDistant(root, 2); return 0; } // This code is contributed by rathbhupendra |
C
#include <stdio.h> #include <stdlib.h> /* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { int data; struct node* left; struct node* right; }; void printKDistant( struct node *root , int k) { if (root == NULL|| k < 0 ) return ; if ( k == 0 ) { printf ( "%d " , root->data ); return ; } printKDistant( root->left, k-1 ) ; printKDistant( root->right, k-1 ) ; } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode( int data) { struct node* node = ( struct node*) malloc ( sizeof ( struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node); } /* Driver program to test above functions*/ int main() { /* Constructed binary tree is 1 / 2 3 / / 4 5 8 */ struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(8); printKDistant(root, 2); getchar (); return 0; } |
JAVA
// Java program to print nodes at k distance from root /* A binary tree node has data, pointer to left child and a pointer to right child */ class Node { int data; Node left, right; Node( int item) { data = item; left = right = null ; } } class BinaryTree { Node root; void printKDistant(Node node, int k) { if (node == null || k < 0 ) //Base case return ; if (k == 0 ) { System.out.print(node.data + " " ); return ; } //recursively traversing printKDistant(node.left, k - 1 ); printKDistant(node.right, k - 1 ); } /* Driver program to test above functions */ public static void main(String args[]) { BinaryTree tree = new BinaryTree(); /* Constructed binary tree is 1 / 2 3 / / 4 5 8 */ tree.root = new Node( 1 ); tree.root.left = new Node( 2 ); tree.root.right = new Node( 3 ); tree.root.left.left = new Node( 4 ); tree.root.left.right = new Node( 5 ); tree.root.right.left = new Node( 8 ); tree.printKDistant(tree.root, 2 ); } } // This code has been contributed by Mayank Jaiswal |
Python3
# Python program to find the nodes at k distance from root # A Binary tree node class Node: # Constructor to create a new node def __init__( self , data): self .data = data self .left = None self .right = None def printKDistant(root, k): if root is None : return if k = = 0 : print (root.data,end = ' ' ) else : printKDistant(root.left, k - 1 ) printKDistant(root.right, k - 1 ) # Driver program to test above function """ Constructed binary tree is 1 / 2 3 / / 4 5 8 """ root = Node( 1 ) root.left = Node( 2 ) root.right = Node( 3 ) root.left.left = Node( 4 ) root.left.right = Node( 5 ) root.right.left = Node( 8 ) printKDistant(root, 2 ) # This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
using System; // c# program to print nodes at k distance from root /* 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; public Node( int item) { data = item; left = right = null ; } } public class BinaryTree { public Node root; public virtual void printKDistant(Node node, int k) { if (node == null || k < 0 ) { return ; } if (k == 0) { Console.Write(node.data + " " ); return ; } printKDistant(node.left, k - 1); printKDistant(node.right, k - 1); } /* Driver program to test above functions */ public static void Main( string [] args) { BinaryTree tree = new BinaryTree(); /* Constructed binary tree is 1 / 2 3 / / 4 5 8 */ tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.right.left = new Node(8); tree.printKDistant(tree.root, 2); } } // This code is contributed by Shrikant13 |
Javascript
<script> // Javascript program to print nodes at k distance from root /* A binary tree node has data, pointer to left child and a pointer to right child */ class Node { constructor(item) { this .data = item; this .left = null ; this .right = null ; } } var root = null ; function printKDistant(node, k) { if (node == null || k < 0 ) { return ; } if (k == 0) { document.write(node.data + " " ); return ; } printKDistant(node.left, k - 1); printKDistant(node.right, k - 1); } /* Driver program to test above functions */ /* Constructed binary tree is 1 / 2 3 / / 4 5 8 */ root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(8); printKDistant(root, 2); // This code is contributed by importantly. </script> |
输出
4 5 8
时间复杂性： O（n），其中n是给定二叉树中的节点数。
空间复杂性： O（二叉树的高度）。
注释-
- 如果是真的，请打印节点—— 始终在每个节点检查K距离==0
- 左或右子树—— 传递到其子树时，将距离减少1
另一种方法 –我们可以进行级别顺序遍历并跟踪级别。当当前级别等于k时，打印该级别的所有节点。
Python3
# Python program to find the nodes at k distance from root # A Binary tree node class Node: # Constructor to create a new node def __init__( self , data): self .data = data self .left = None self .right = None def printKDistant(root, k): # check if root is None if root is None : return q = [] # ans = [] q.append(root) lvl = 0 # tracking of level while (q): n = len (q) # when lvl becomes k we add all values of q in ans. if lvl = = k: for i in range (n): print ((q[i].data), end = " " ) return for i in range ( 1 , n + 1 ): temp = q.pop( 0 ) if temp.left: q.append(temp.left) if temp.right: q.append(temp.right) lvl + = 1 # if after traversing ,if lvl is less than k , # that means nodes at k distance does not exist. if lvl < k: return # Driver program to test above function """ Constructed binary tree is 1 / 2 3 / / 4 5 8 """ root = Node( 1 ) root.left = Node( 2 ) root.right = Node( 3 ) root.left.left = Node( 4 ) root.left.right = Node( 5 ) root.right.left = Node( 8 ) printKDistant(root, 2 ) #this code is contributed by Vivek Maddeshiya |
输出
4 5 8
时间复杂性 ：O（n），其中n是给定二叉树中的节点数。
如果您发现上述代码/算法不正确，请写评论，或者找到更好的方法来解决相同的问题。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
