原文:
给定一棵二叉树和一个正整数 k，打印距离叶节点距离为 k 的所有节点。 这里距离的含义与不同。这里离叶子的 k 距离意味着比叶子节点高 k 级。例如，如果 k 大于二叉树的高度，那么就不应该打印任何东西。预期时间复杂度为 o(n)，其中 n 是给定二叉树中的节点数。
这个想法是遍历树。继续存储所有祖先，直到我们碰到一个叶节点。当我们到达一个叶节点时，我们在距离 k 处打印祖先。我们还需要跟踪已经打印为输出的节点。为此，我们使用了一个布尔数组。
c
/* program to print all nodes
which are at distance k from a leaf */
#include
using namespace std;
#define max_height 10000
struct node {
int key;
node *left, *right;
};
/* utility that allocates a new node with the given key */
node* newnode(int key)
{
node* node = new node;
node->key = key;
node->left = node->right = null;
return (node);
}
/* this function prints all nodes that are distance k from a leaf node
path[] --> store ancestors of a node
visited[] --> stores true if a node is printed as output. a node may be k
distance away from many leaves, we want to print it once */
void kdistantfromleafutil(node* node, int path[], bool visited[],
int pathlen, int k)
{
// base case
if (node == null)
return;
/* append this node to the path array */
path[pathlen] = node->key;
visited[pathlen] = false;
pathlen ;
/* it's a leaf, so print the ancestor at distance k only
if the ancestor is not already printed */
if (node->left == null &&
node->right == null &&
pathlen - k - 1 >= 0 &&
visited[pathlen - k - 1] == false)
{
cout << path[pathlen - k - 1] << " ";
visited[pathlen - k - 1] = true;
return;
}
/* if not leaf node, recur for left and right subtrees */
kdistantfromleafutil(node->left, path, visited, pathlen, k);
kdistantfromleafutil(node->right, path, visited, pathlen, k);
}
/* given a binary tree and a number k, print all nodes that are k
distant from a leaf*/
void printkdistantfromleaf(node* node, int k)
{
int path[max_height];
bool visited[max_height] = { false };
kdistantfromleafutil(node, path, visited, 0, k);
}
/* driver code*/
int main()
{
// let us create binary tree
// given in the above example
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(6);
root->right->right = newnode(7);
root->right->left->right = newnode(8);
cout << "nodes at distance 2 are: ";
printkdistantfromleaf(root, 2);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print all nodes at a distance k from leaf
// a binary tree node
class node {
int data;
node left, right;
node(int item)
{
data = item;
left = right = null;
}
}
class binarytree {
node root;
/* this function prints all nodes that are distance k from a leaf node
path[] --> store ancestors of a node
visited[] --> stores true if a node is printed as output. a node may
be k distance away from many leaves, we want to print it once */
void kdistantfromleafutil(node node, int path[], boolean visited[],
int pathlen, int k)
{
// base case
if (node == null)
return;
/* append this node to the path array */
path[pathlen] = node.data;
visited[pathlen] = false;
pathlen ;
/* it's a leaf, so print the ancestor at distance k only
if the ancestor is not already printed */
if (node.left == null && node.right == null
&& pathlen - k - 1 >= 0 && visited[pathlen - k - 1] == false) {
system.out.print(path[pathlen - k - 1] " ");
visited[pathlen - k - 1] = true;
return;
}
/* if not leaf node, recur for left and right subtrees */
kdistantfromleafutil(node.left, path, visited, pathlen, k);
kdistantfromleafutil(node.right, path, visited, pathlen, k);
}
/* given a binary tree and a number k, print all nodes that are k
distant from a leaf*/
void printkdistantfromleaf(node node, int k)
{
int path[] = new int[1000];
boolean visited[] = new boolean[1000];
kdistantfromleafutil(node, path, visited, 0, k);
}
// 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(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(6);
tree.root.right.right = new node(7);
tree.root.right.left.right = new node(8);
system.out.println(" nodes at distance 2 are :");
tree.printkdistantfromleaf(tree.root, 2);
}
}
// this code has been contributed by mayank jaiswal
python 3
# program to print all nodes which are at
# distance k from a leaf
# utility that allocates a new node with
# the given key
class newnode:
def __init__(self, key):
self.key = key
self.left = self.right = none
# this function prints all nodes that
# are distance k from a leaf node
# path[] -. store ancestors of a node
# visited[] -. stores true if a node is
# printed as output. a node may be k distance
# away from many leaves, we want to print it once
def kdistantfromleafutil(node, path, visited,
pathlen, k):
# base case
if (node == none):
return
# append this node to the path array
path[pathlen] = node.key
visited[pathlen] = false
pathlen = 1
# it's a leaf, so print the ancestor at
# distance k only if the ancestor is
# not already printed
if (node.left == none and node.right == none and
pathlen - k - 1 >= 0 and
visited[pathlen - k - 1] == false):
print(path[pathlen - k - 1], end = " ")
visited[pathlen - k - 1] = true
return
# if not leaf node, recur for left
# and right subtrees
kdistantfromleafutil(node.left, path,
visited, pathlen, k)
kdistantfromleafutil(node.right, path,
visited, pathlen, k)
# given a binary tree and a number k,
# print all nodes that are k distant from a leaf
def printkdistantfromleaf(node, k):
global max_height
path = [none] * max_height
visited = [false] * max_height
kdistantfromleafutil(node, path, visited, 0, k)
# driver code
max_height = 10000
# let us create binary tree given in
# the above example
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(6)
root.right.right = newnode(7)
root.right.left.right = newnode(8)
print("nodes at distance 2 are:", end = " ")
printkdistantfromleaf(root, 2)
# this code is contributed by pranchalk
c
using system;
// c# program to print all nodes at a distance k from leaf
// 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;
/* this function prints all nodes that are distance k from a leaf node
path[] --> store ancestors of a node
visited[] --> stores true if a node is printed as output. a node may
be k distance away from many leaves, we want to print it once */
public virtual void kdistantfromleafutil(node node, int[] path, bool[] visited, int pathlen, int k)
{
// base case
if (node == null) {
return;
}
/* append this node to the path array */
path[pathlen] = node.data;
visited[pathlen] = false;
pathlen ;
/* it's a leaf, so print the ancestor at distance k only
if the ancestor is not already printed */
if (node.left == null && node.right == null && pathlen - k - 1 >= 0 && visited[pathlen - k - 1] == false) {
console.write(path[pathlen - k - 1] " ");
visited[pathlen - k - 1] = true;
return;
}
/* if not leaf node, recur for left and right subtrees */
kdistantfromleafutil(node.left, path, visited, pathlen, k);
kdistantfromleafutil(node.right, path, visited, pathlen, k);
}
/* given a binary tree and a number k, print all nodes that are k
distant from a leaf*/
public virtual void printkdistantfromleaf(node node, int k)
{
int[] path = new int[1000];
bool[] visited = new bool[1000];
kdistantfromleafutil(node, path, visited, 0, k);
}
// 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(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(6);
tree.root.right.right = new node(7);
tree.root.right.left.right = new node(8);
console.writeline(" nodes at distance 2 are :");
tree.printkdistantfromleaf(tree.root, 2);
}
}
// this code is contributed by shrikant13
java 描述语言
output
nodes at distance 2 are: 1 3
时间复杂度:上述代码的时间复杂度为 o(n)，因为代码进行简单的树遍历。
空间优化解:
c
// c program to print all nodes at a distance k from leaf
// a binary tree node
#include
using namespace std;
struct node
{
int data;
node *left, *right;
};
// utility function to
// create a new tree node
node* newnode(int key)
{
node *temp = new node;
temp->data= key;
temp->left = temp->right = null;
return temp;
}
/* given a binary tree and a number k,
print all nodes that are k
distant from a leaf*/
int printkdistantfromleaf(struct node *node, int k)
{
if (node == null)
return -1;
int lk = printkdistantfromleaf(node->left, k);
int rk = printkdistantfromleaf(node->right, k);
bool isleaf = lk == -1 && lk == rk;
if (lk == 0 || rk == 0 || (isleaf && k == 0))
cout<<(" " )<<( node->data);
if (isleaf && k > 0)
return k - 1; // leaf node
if (lk > 0 && lk < k)
return lk - 1; // parent of left leaf
if (rk > 0 && rk < k)
return rk - 1; // parent of right leaf
return -2;
}
// driver code
int main()
{
node *root = null;
/* let us construct the tree shown in above diagram */
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(6);
root->right->right = newnode(7);
root->right->left->right = newnode(8);
cout << (" nodes at distance 2 are :") << endl;
printkdistantfromleaf(root, 2);
}
// this code contributed by aashish1995
java 语言(一种计算机语言，尤用于创建网站)
// java program to print all nodes at a distance k from leaf
// a binary tree node
class node {
int data;
node left, right;
node(int item)
{
data = item;
left = right = null;
}
}
class binarytree {
node root;
/* given a binary tree and a nuber k, print all nodes that are k
distant from a leaf*/
int printkdistantfromleaf(node node, int k)
{
if (node == null)
return -1;
int lk = printkdistantfromleaf(node.left, k);
int rk = printkdistantfromleaf(node.right, k);
boolean isleaf = lk == -1 && lk == rk;
if (lk == 0 || rk == 0 || (isleaf && k == 0))
system.out.print(" " node.data);
if (isleaf && k > 0)
return k - 1; // leaf node
if (lk > 0 && lk < k)
return lk - 1; // parent of left leaf
if (rk > 0 && rk < k)
return rk - 1; // parent of right leaf
return -2;
}
// 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(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(6);
tree.root.right.right = new node(7);
tree.root.right.left.right = new node(8);
system.out.println(" nodes at distance 2 are :");
tree.printkdistantfromleaf(tree.root, 2);
}
}
// this code has been contributed by vijayan annamalai
c
// c# program to print all nodes at a distance k from leaf
// a binary tree node
using system;
class node {
public int data;
public node left, right;
public node(int item)
{
data = item;
left = right = null;
}
}
class binarytree {
node root;
/* given a binary tree and a nuber k, print all nodes that are k
distant from a leaf*/
int printkdistantfromleaf(node node, int k)
{
if (node == null)
return -1;
int lk = printkdistantfromleaf(node.left, k);
int rk = printkdistantfromleaf(node.right, k);
bool isleaf = lk == -1 && lk == rk;
if (lk == 0 || rk == 0 || (isleaf && k == 0))
console.write(" " node.data);
if (isleaf && k > 0)
return k - 1; // leaf node
if (lk > 0 && lk < k)
return lk - 1; // parent of left leaf
if (rk > 0 && rk < k)
return rk - 1; // parent of right leaf
return -2;
}
// 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(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(6);
tree.root.right.right = new node(7);
tree.root.right.left.right = new node(8);
console.write("nodes at distance 2 are :");
tree.printkdistantfromleaf(tree.root, 2);
}
}
// this code is contributed by rutvik_56
java 描述语言
output
nodes at distance 2 are :
3 1
发现有不正确的地方请写评论，或者想分享更多以上讨论话题的信息
另一种方法:
c
// print all nodes that are at distance k from a leaf node
#include
using namespace std;
struct bstnode {
int data;
bstnode* right;
bstnode* left;
};
bstnode* newnode(int data)
{
bstnode* temp = new bstnode();
temp->data = data;
temp->right = temp->left = null;
return temp;
}
void del(bstnode* root)
{
if (root != null) {
del(root->left);
del(root->right);
delete root;
}
}
int printk(bstnode* root, int k)
{
if (root == null)
return 0;
int l = printk(root->left, k);
int r = printk(root->right, k);
if (l == k || r == k)
cout << root->data << " ";
return 1 max(l, r);
}
int main()
{
bstnode* root = null;
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(6);
root->right->right = newnode(7);
root->right->left->right = newnode(8);
// root->right->right->right=newnode(9);
int k = 2;
printk(root, k);
del(root);
return 0;
}
output
3 1
时间复杂度: o(n)作为代码做一个简单的树遍历。 辅助 空间:使用 o(h)作为函数调用栈，其中 h =树的高度。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
