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

本文概述

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

给定树的根和整数k。打印所有与根距离为k的节点。
例如, 在下面的树中, 4、5和8与根的距离为2。

1/\23/\/458

推荐：请在"实践首先, 在继续解决方案之前。可以使用递归来解决该问题。感谢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 = https://www.lsbin.com/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 / \ 23 / \/ 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

#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 = https://www.lsbin.com/data; node-> left = NULL; node-> right = NULL; return (node); }/* Driver program to test above functions*/ int main() {/* Constructed binary tree is 1 / 23 // 458 */ 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 = https://www.lsbin.com/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 /\ 23 /\/ 45 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 = https://www.lsbin.com/data self .left = None self .right = Nonedef 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 /\ 23 /\/ 458 """ 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)

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 = https://www.lsbin.com/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 /\ 23 /\/ 45 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

输出如下：