你将获得一个名为printKDistanceNodes的函数，它接受二叉树的根节点、起始节点和整数K作为输入参数。请完成该函数，以按排序顺序打印从给定起始节点K距离的所有节点（每行一个）。距离可能向上或向下。请注意保留HTML标记。
7个回答
3
private void printNodeAtN(Node root, Node start, int k) {
if (root != null) {
// calculate if the start is in left or right subtree - if start is
// root this variable is null
Boolean left = isLeft(root, start);
int depth = depth(root, start, 0);
if (depth == -1)
return;
printNodeDown(root, k);
if (root == start)
return;
if (left) {
if (depth > k) {
// print the nodes at depth-k level in left tree
printNode(depth - k - 1, root.left);
} else if (depth < k) {
// print the nodes at right tree level k-depth
printNode(k - depth - 1, root.right);
} else {
System.out.println(root.data);
}
} else {
// similar if the start is in right subtree
if (depth > k) {
// print the nodes at depth-k level in left tree
printNode(depth - k - 1, root.right);
} else if (depth < k) {
// print the nodes at right tree level k-depth
printNode(k - depth - 1, root.left);
} else {
System.out.println(root.data);
}
}
}
}
// print the nodes at depth - "level" from root
void printNode(int level, Node root) {
if (level == 0 && root != null) {
System.out.println(root.data);
} else {
printNode(level - 1, root.left);
printNode(level - 1, root.right);
}
}
// print the children of the start
void printNodeDown(Node start, int k) {
if (start != null) {
if (k == 0) {
System.out.println(start.data);
}
printNodeDown(start.left, k - 1);
printNodeDown(start.right, k - 1);
}
}
private int depth(Node root, Node node, int d) {
if (root == null)
return -1;
if (root != null && node == root) {
return d;
} else {
int left = depth(root.left, node, d + 1);
int right = depth(root.right, node, d + 1);
if (left > right)
return left;
else
return right;
}
}
- Vinay Kumar
1
在距离为K的位置上最多只有一个节点，该节点向上 - 从起始节点开始向上移动K步。将其添加到排序数据结构中。
然后需要添加向下的节点。为此，可以使用队列进行BFS，其中在将节点插入队列时，将深度与节点一起存储（起始节点位于第0级，其子节点位于第1级等）。然后，当弹出节点时，如果它们在第K级，则将它们添加到排序数据结构中。当您开始弹出第K + 1级的节点时，可以停止。
最后，打印来自排序数据结构的节点（它们将被排序）。
编辑：如果没有父指针：
编写一个递归函数int Go(Node node)，它返回相对于传入节点的起始节点的深度，如果节点的子树不包含起始节点，则返回-1。该函数将作为副作用找到第K个父节点。伪代码：
static Node KthParent = null;
static Node start = ...;
static int K = ...;
int Go(Node node) {
if (node == start) return 0;
intDepth = -1;
if(node.LeftChild != null) {
int leftDepth = Go(node.LeftChild);
if(leftDepth >= 0) intDepth = leftDepth+1;
}
if (intDepth < 0 && node.rightChild != null) {
int rightDepth = Go(node.RightChild);
if(rightDepth >= 0) intDepth = rightDepth+1;
}
if(intDepth == K) KthParent = node;
return intDepth;
}
- Petar Ivanov
2
我有一个问题，假设我们有一棵简单的树（根节点为1，左子节点为2，右子节点为3），左子节点和右子节点之间的距离是否应该等于2。 - J.W.
距离为K的节点上方最多只有一个错误。例如，查找到x的距离为2，假设x是父节点的左子节点，那么父节点的右子节点距离x有2步之远，如果它不为空，则该节点上方最多只有一个错误。 - Jackson Tale
0
struct node{
int data;
node* left;
node* right;
bool printed;
};
void print_k_dist(node** root,node** p,int k,int kmax);
void reinit_printed(node **root);
void print_k_dist(node** root,node **p,int k,int kmax)
{
if(*p==NULL) return;
node* par=parent(root,p);
if(k<=kmax &&(*p)->printed==0)
{
cout<<(*p)->data<<" ";
(*p)->printed=1;
k++;
print_k_dist(root,&par,k,kmax);
print_k_dist(root,&(*p)->left,k,kmax);
print_k_dist(root,&(*p)->right,k,kmax);
}
else
return;
}
void reinit_printed(node **root)
{
if(*root==NULL) return;
else
{
(*root)->printed=0;
reinit_printed(&(*root)->left);
reinit_printed(&(*root)->right);
}
}
- mandeep
0
typedef struct node
{
int data;
struct node *left;
struct node *right;
}node;
void printkdistanceNodeDown(node *n, int k)
{
if(!n)
return ;
if(k==0)
{
printf("%d\n",n->data);
return;
}
printkdistanceNodeDown(n->left,k-1);
printkdistanceNodeDown(n->right,k-1);
}
void printkdistanceNodeDown_fromUp(node* target ,int *k)
{
if(!target)
return ;
if(*k==0)
{
printf("%d\n",target->data);
return;
}
else
{
int val=*k;
printkdistanceNodeDown(target,val-1);
}
}
int printkdistanceNodeUp(node* root, node* n , int k)
{
if(!root)
return 0;
if(root->data==n->data)
return 1;
int pl=printkdistanceNodeUp(root->left,n,k);
int pr=printkdistanceNodeUp(root->right,n,k);
if(pl )
{
k--;
if(k==0)
printf("%d\n",root->data);
else
{
printkdistanceNodeDown_fromUp(root->right,k);
printkdistanceNodeDown_fromUp(root->left,k-1);
}
return 1;
}
if(pr )
{
k--;
if(k==0)
printf("%d\n",root->data);
else
{
printkdistanceNodeDown_fromUp(root->left,k);
printkdistanceNodeDown_fromUp(root->right,k-1);
}
return 1;
}
return 0;
}
void printkdistanceNode(node* root, node* n , int k )
{
if(!root)
return ;
int val=k;
printkdistanceNodeUp(root,n,k);
printkdistanceNodeDown(n,val);
}
调用函数：printkdistanceNode(root,n,k);
输出将打印给定节点向上和向下距离为k的所有节点。
- Shirdi_Sai
0
这是一个完整的Java程序。灵感来自于geeksforgeeks算法
// Java program to print all nodes at a distance k from given node
class BinaryTreePrintKDistance {
Node root;
/*
* Recursive function to print all the nodes at distance k in tree (or
* subtree) rooted with given root.
*/
void printKDistanceForDescendant(Node targetNode, int currentDist,
int inputDist) {
// Base Case
if (targetNode == null || currentDist > inputDist)
return;
// If we reach a k distant node, print it
if (currentDist == inputDist) {
System.out.print(targetNode.data);
System.out.println("");
return;
}
++currentDist;
// Recur for left and right subtrees
printKDistanceForDescendant(targetNode.left, currentDist, inputDist);
printKDistanceForDescendant(targetNode.right, currentDist, inputDist);
}
public int printkdistance(Node targetNode, Node currentNode,
int inputDist) {
if (currentNode == null) {
return -1;
}
if (targetNode.data == currentNode.data) {
printKDistanceForDescendant(currentNode, 0, inputDist);
return 0;
}
int ld = printkdistance(targetNode, currentNode.left, inputDist);
if (ld != -1) {
if (ld + 1 == inputDist) {
System.out.println(currentNode.data);
} else {
printKDistanceForDescendant(currentNode.right, 0, inputDist
- ld - 2);
}
return ld + 1;
}
int rd = printkdistance(targetNode, currentNode.right, inputDist);
if (rd != -1) {
if (rd + 1 == inputDist) {
System.out.println(currentNode.data);
} else {
printKDistanceForDescendant(currentNode.left, 0, inputDist - rd
- 2);
}
return rd + 1;
}
return -1;
}
// Driver program to test the above functions
@SuppressWarnings("unchecked")
public static void main(String args[]) {
BinaryTreePrintKDistance tree = new BinaryTreePrintKDistance();
/* Let us construct the tree shown in above diagram */
tree.root = new Node(20);
tree.root.left = new Node(8);
tree.root.right = new Node(22);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(12);
tree.root.left.right.left = new Node(10);
tree.root.left.right.right = new Node(14);
Node target = tree.root.left;
tree.printkdistance(target, tree.root, 2);
}
static class Node<T> {
public Node left;
public Node right;
public T data;
Node(T data) {
this.data = data;
}
}
}
- M Sach
0
private static int printNodeAtK(Node root, Node start, int k, boolean found){
if(root != null){
if(k == 0 && found){
System.out.println(root.data);
}
if(root==start || found == true){
int leftd = printNodeAtK(root.left, start, k-1, true);
int rightd = printNodeAtK(root.right,start,k-1,true);
return 1;
}else{
int leftd = printNodeAtK(root.left, start, k, false);
int rightd = printNodeAtK(root.right,start,k,false);
if(leftd == k || rightd == k){
System.out.println(root.data);
}
if(leftd != -1 && leftd > rightd){
return leftd+1;
}else if(rightd != -1 && rightd>leftd){
return rightd+1;
}else{
return -1;
}
}
}
return -1;
}
- jayesh
0
在这段代码中，PrintNodesAtKDistance 首先会尝试找到所需的节点。
if(root.value == requiredNode)
当我们找到所需节点时，我们打印距离该节点K的所有子节点。
现在我们的任务是打印所有在其他分支中的节点（向上走并打印）。我们返回-1直到我们找到所需节点。当我们得到所需节点时，我们获得lPath或rPath >=0。现在我们必须打印距离(lPath/rPath) -1的所有节点。
public void PrintNodes(Node Root, int requiredNode, int iDistance)
{
PrintNodesAtKDistance(Root, requiredNode, iDistance);
}
public int PrintNodesAtKDistance(Node root, int requiredNode, int iDistance)
{
if ((root == null) || (iDistance < 0))
return -1;
int lPath = -1, rPath = -1;
if(root.value == requiredNode)
{
PrintChildNodes(root, iDistance);
return iDistance - 1;
}
lPath = PrintNodesAtKDistance(root.left, requiredNode, iDistance);
rPath = PrintNodesAtKDistance(root.right, requiredNode, iDistance);
if (lPath > 0)
{
PrintChildNodes(root.right, lPath - 1);
return lPath - 1;
}
else if(lPath == 0)
{
Debug.WriteLine(root.value);
}
if(rPath > 0)
{
PrintChildNodes(root.left, rPath - 1);
return rPath - 1;
}
else if (rPath == 0)
{
Debug.WriteLine(root.value);
}
return -1;
}
public void PrintChildNodes(Node aNode, int iDistance)
{
if (aNode == null)
return;
if(iDistance == 0)
{
Debug.WriteLine(aNode.value);
}
PrintChildNodes(aNode.left, iDistance - 1);
PrintChildNodes(aNode.right, iDistance - 1);
}
- Mac
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接