算法：如何打印树中所有到根的距离为k的节点？

本文概述

• 建议：在继续解决方案之前, 请先在"实践"上解决它。
• C ++
• C
• Java
• python
• C#

给定树的根和整数k。打印所有与根距离为k的节点。

例如, 在下面的树中, 4、5和8与根的距离为2。

1
          /   \
        2      3
      /  \    /
    4     5  8

推荐：请在"实践首先, 在继续解决方案之前。

可以使用递归来解决该问题。感谢eldho提出解决方案。

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) 
         return ; 
     if ( k == 0 ) 
     { 
         cout << root->data << " " ; 
         return ; 
     } 
     else
     { 
         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) 
       return ;
    if ( k == 0 )
    {
       printf ( "%d " , root->data );
       return ;
    }
    else
    {      
       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 )
             return ;
         if (k == 0 ) 
         {
             System.out.print(node.data + " " );
             return ;
         } 
         else 
         {
             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

python

# 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, 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 )
         {
             return ;
         }
         if (k == 0)
         {
             Console.Write(node.data + " " );
             return ;
         }
         else
         {
             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

输出如下：

4 5 8

时间复杂度：O(n)其中n是给定二叉树中的节点数。

如果你发现上述代码/算法有误, 请写注释, 或者找到解决同一问题的更好方法。