原文:
给定一棵二叉树、二叉树中的一个目标节点和一个整数值 k，打印所有与给定目标节点相距 k 的节点。没有可用的父指针。
考虑图 所示的树输入:target =指向数据为 8 的节点的指针。 根=指向数据为 20 的节点的指针。 k = 2。 输出:10 14 22 如果目标是 14，k 是 3，那么输出 应该是“4 20”
有两种类型的节点需要考虑。 1) 子树中以目标节点为根的节点。例如，如果目标节点是 8，k 是 2，那么这样的节点是 10 和 14。 2) 其他节点，可能是目标的祖先，或者某个其他子树中的节点。对于目标节点 8，k 是 2，节点 22 属于这一类。 找到第一类节点很容易实现。只需遍历以目标节点为根的子树，并在递归调用中递减 k。当 k 变为 0 时，打印当前正在遍历的节点(详见)。这里我们称函数为printkdistancenodedown()。 如何找到第二类节点？对于不在以目标节点为根的子树中的输出节点，我们必须遍历所有祖先。对于每个祖先，我们找到它与目标节点的距离，让距离为 d，现在我们去祖先的其他子树(如果在左子树中找到目标，那么我们去右子树，反之亦然)并找到离祖先 k-d 距离的所有节点。
下面是上述方法的实现。
c
#include
using namespace std;
// a binary tree node
struct node
{
int data;
struct node *left, *right;
};
/* recursive function to print all the nodes at distance k in the
tree (or subtree) rooted with given root. see */
void printkdistancenodedown(node *root, int k)
{
// base case
if (root == null || k < 0) return;
// if we reach a k distant node, print it
if (k==0)
{
cout << root->data << endl;
return;
}
// recur for left and right subtrees
printkdistancenodedown(root->left, k-1);
printkdistancenodedown(root->right, k-1);
}
// prints all nodes at distance k from a given target node.
// the k distant nodes may be upward or downward. this function
// returns distance of root from target node, it returns -1 if target
// node is not present in tree rooted with root.
int printkdistancenode(node* root, node* target , int k)
{
// base case 1: if tree is empty, return -1
if (root == null) return -1;
// if target is same as root. use the downward function
// to print all nodes at distance k in subtree rooted with
// target or root
if (root == target)
{
printkdistancenodedown(root, k);
return 0;
}
// recur for left subtree
int dl = printkdistancenode(root->left, target, k);
// check if target node was found in left subtree
if (dl != -1)
{
// if root is at distance k from target, print root
// note that dl is distance of root's left child from target
if (dl 1 == k)
cout << root->data << endl;
// else go to right subtree and print all k-dl-2 distant nodes
// note that the right child is 2 edges away from left child
else
printkdistancenodedown(root->right, k-dl-2);
// add 1 to the distance and return value for parent calls
return 1 dl;
}
// mirror of above code for right subtree
// note that we reach here only when node was not found in left subtree
int dr = printkdistancenode(root->right, target, k);
if (dr != -1)
{
if (dr 1 == k)
cout << root->data << endl;
else
printkdistancenodedown(root->left, k-dr-2);
return 1 dr;
}
// if target was neither present in left nor in right subtree
return -1;
}
// a utility function to create a new binary tree node
node *newnode(int data)
{
node *temp = new node;
temp->data = data;
temp->left = temp->right = null;
return temp;
}
// driver program to test above functions
int main()
{
/* let us construct the tree shown in above diagram */
node * root = newnode(20);
root->left = newnode(8);
root->right = newnode(22);
root->left->left = newnode(4);
root->left->right = newnode(12);
root->left->right->left = newnode(10);
root->left->right->right = newnode(14);
node * target = root->left->right;
printkdistancenode(root, target, 2);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print all nodes at a distance k from given node
// a binary tree node
class node
{
int data;
node left, right;
node(int item)
{
data = item;
left = right = null;
}
}
class binarytree
{
node root;
/* recursive function to print all the nodes at distance k in
tree (or subtree) rooted with given root. */
void printkdistancenodedown(node node, int k)
{
// base case
if (node == null || k < 0)
return;
// if we reach a k distant node, print it
if (k == 0)
{
system.out.print(node.data);
system.out.println("");
return;
}
// recur for left and right subtrees
printkdistancenodedown(node.left, k - 1);
printkdistancenodedown(node.right, k - 1);
}
// prints all nodes at distance k from a given target node.
// the k distant nodes may be upward or downward.this function
// returns distance of root from target node, it returns -1
// if target node is not present in tree rooted with root.
int printkdistancenode(node node, node target, int k)
{
// base case 1: if tree is empty, return -1
if (node == null)
return -1;
// if target is same as root. use the downward function
// to print all nodes at distance k in subtree rooted with
// target or root
if (node == target)
{
printkdistancenodedown(node, k);
return 0;
}
// recur for left subtree
int dl = printkdistancenode(node.left, target, k);
// check if target node was found in left subtree
if (dl != -1)
{
// if root is at distance k from target, print root
// note that dl is distance of root's left child from
// target
if (dl 1 == k)
{
system.out.print(node.data);
system.out.println("");
}
// else go to right subtree and print all k-dl-2 distant nodes
// note that the right child is 2 edges away from left child
else
printkdistancenodedown(node.right, k - dl - 2);
// add 1 to the distance and return value for parent calls
return 1 dl;
}
// mirror of above code for right subtree
// note that we reach here only when node was not found in left
// subtree
int dr = printkdistancenode(node.right, target, k);
if (dr != -1)
{
if (dr 1 == k)
{
system.out.print(node.data);
system.out.println("");
}
else
printkdistancenodedown(node.left, k - dr - 2);
return 1 dr;
}
// if target was neither present in left nor in right subtree
return -1;
}
// driver program to test the above functions
public static void main(string args[])
{
binarytree tree = new binarytree();
/* 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.right;
tree.printkdistancenode(tree.root, target, 2);
}
}
// this code has been contributed by mayank jaiswal
计算机编程语言
# python program to print nodes at distance k from a given node
# a binary tree node
class node:
# a constructor to create a new node
def __init__(self, data):
self.data = data
self.left = none
self.right = none
# recursive function to print all the nodes at distance k
# int the tree(or subtree) rooted with given root. see
def printkdistancenodedown(root, k):
# base case
if root is none or k< 0 :
return
# if we reach a k distant node, print it
if k == 0 :
print root.data
return
# recur for left and right subtree
printkdistancenodedown(root.left, k-1)
printkdistancenodedown(root.right, k-1)
# prints all nodes at distance k from a given target node
# the k distant nodes may be upward or downward. this function
# returns distance of root from target node, it returns -1
# if target node is not present in tree rooted with root
def printkdistancenode(root, target, k):
# base case 1 : if tree is empty return -1
if root is none:
return -1
# if target is same as root. use the downward function
# to print all nodes at distance k in subtree rooted with
# target or root
if root == target:
printkdistancenodedown(root, k)
return 0
# recur for left subtree
dl = printkdistancenode(root.left, target, k)
# check if target node was found in left subtree
if dl != -1:
# if root is at distance k from target, print root
# note: dl is distance of root's left child
# from target
if dl 1 == k :
print root.data
# else go to right subtreee and print all k-dl-2
# distant nodes
# note: that the right child is 2 edges away from
# left chlid
else:
printkdistancenodedown(root.right, k-dl-2)
# add 1 to the distance and return value for
# for parent calls
return 1 dl
# mirror of above code for right subtree
# note that we reach here only when node was not found
# in left subtree
dr = printkdistancenode(root.right, target, k)
if dr != -1:
if (dr 1 == k):
print root.data
else:
printkdistancenodedown(root.left, k-dr-2)
return 1 dr
# if target was neither present in left nor in right subtree
return -1
# driver program to test above function
root = node(20)
root.left = node(8)
root.right = node(22)
root.left.left = node(4)
root.left.right = node(12)
root.left.right.left = node(10)
root.left.right.right = node(14)
target = root.left.right
printkdistancenode(root, target, 2)
# this code is contributed by nikhil kumar singh(nickzuck_007)
c
using system;
// c# program to print all nodes at a distance k from given node
// a binary tree node
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;
/* recursive function to print all the nodes at distance k in
tree (or subtree) rooted with given root. */
public virtual void printkdistancenodedown(node node, int k)
{
// base case
if (node == null || k < 0)
{
return;
}
// if we reach a k distant node, print it
if (k == 0)
{
console.write(node.data);
console.writeline("");
return;
}
// recur for left and right subtrees
printkdistancenodedown(node.left, k - 1);
printkdistancenodedown(node.right, k - 1);
}
// prints all nodes at distance k from a given target node.
// the k distant nodes may be upward or downward.this function
// returns distance of root from target node, it returns -1
// if target node is not present in tree rooted with root.
public virtual int printkdistancenode(node node, node target, int k)
{
// base case 1: if tree is empty, return -1
if (node == null)
{
return -1;
}
// if target is same as root. use the downward function
// to print all nodes at distance k in subtree rooted with
// target or root
if (node == target)
{
printkdistancenodedown(node, k);
return 0;
}
// recur for left subtree
int dl = printkdistancenode(node.left, target, k);
// check if target node was found in left subtree
if (dl != -1)
{
// if root is at distance k from target, print root
// note that dl is distance of root's left child from
// target
if (dl 1 == k)
{
console.write(node.data);
console.writeline("");
}
// else go to right subtree and print all k-dl-2 distant nodes
// note that the right child is 2 edges away from left child
else
{
printkdistancenodedown(node.right, k - dl - 2);
}
// add 1 to the distance and return value for parent calls
return 1 dl;
}
// mirror of above code for right subtree
// note that we reach here only when node was not found in left
// subtree
int dr = printkdistancenode(node.right, target, k);
if (dr != -1)
{
if (dr 1 == k)
{
console.write(node.data);
console.writeline("");
}
else
{
printkdistancenodedown(node.left, k - dr - 2);
}
return 1 dr;
}
// if target was neither present in left nor in right subtree
return -1;
}
// driver program to test the above functions
public static void main(string[] args)
{
binarytree tree = new binarytree();
/* 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.right;
tree.printkdistancenode(tree.root, target, 2);
}
}
// this code is contributed by shrikant13
java 描述语言
输出:
4
20
时间复杂度:乍一看时间复杂度看起来比 o(n)还多，但是如果我们仔细看，可以观察到没有一个节点被遍历超过两次。因此时间复杂度为 o(n)。 本文由普拉桑特·库马尔供稿。如果您发现任何不正确的地方，或者您想分享更多关于上面讨论的主题的信息，请写评论
备选方案:
- 从根节点获取路径并添加到列表中
- 对于路径中的每个第 i 个元素，只需迭代并打印第(k-i)个距离节点。
java 语言(一种计算机语言，尤用于创建网站)
import java.io.*;
import java.util.*;
class treenode {
public int val;
public treenode left;
public treenode right;
public treenode() {}
public treenode(int val) { this.val = val; }
}
class gfg {
list path = null;
//finding all the nodes at a distance k from target
//node.
public list distancek(treenode root,
treenode target, int k)
{
path = new arraylist<>();
findpath(root, target);
list result = new arraylist<>();
for (int i = 0; i < path.size(); i ) {
findkdistancefromnode(
path.get(i), k - i, result,
i == 0 ? null : path.get(i - 1));
}
//returning list of all nodes at a distance k
return result;
}
// blocker is used for ancestors node if target at
//left then we have to go in right or if target at
// right then we have to go in left.
public void findkdistancefromnode(treenode node,
int dist,
list result,
treenode blocker)
{
if (dist < 0 || node == null
|| (blocker != null && node == blocker)) {
return;
}
if (dist == 0) {
result.add(node.val);
}
findkdistancefromnode(node.left, dist - 1, result,
blocker);
findkdistancefromnode(node.right, dist - 1, result,
blocker);
}
//finding the path of target node from root node
public boolean findpath(treenode node, treenode target)
{
if (node == null)
return false;
if (node == target || findpath(node.left, target)
|| findpath(node.right, target)) {
path.add(node);
return true;
}
return false;
}
// driver program to test the above functions
public static void main(string[] args)
{
gfg gfg = new gfg();
/* let us construct the tree shown in above diagram */
treenode root = new treenode(20);
root.left = new treenode(8);
root.right = new treenode(22);
root.left.left = new treenode(4);
root.left.right = new treenode(12);
root.left.right.left = new treenode(10);
root.left.right.right = new treenode(14);
treenode target = root.left.right;
system.out.println(gfg.distancek(root, target, 2));
}
}
output
[4, 20]
时间复杂度: o(n)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
