原文:
给出了二叉树和数 k。打印树中的每条路径，路径中节点的和为 k. 一条路径可以从任意节点开始，到任意节点结束，且必须只向下，即不必是根节点和叶节点；负数也可以出现在树中。 例:
input : k = 5
root of below binary tree:
1
/ \
3 -1
/ \ / \
2 1 4 5
/ / \ \
1 1 2 6
output :
3 2
3 1 1
1 3 1
4 1
1 -1 4 1
-1 4 2
5
1 -1 5
来源:
请注意，这个问题与有很大的不同。在这里，每个节点都可以被视为根，因此路径可以在任何节点开始和结束。 解决这个问题的基本思路是对给定的树进行一次前序遍历。我们还需要一个容器(向量)来跟踪通向该节点的路径。在每个节点，我们检查是否有任何与 k 相加的路径，如果有，我们打印路径并递归地打印每个路径。 下面是同样的实现。
c
// c program to print all paths with sum k.
#include
using namespace std;
// utility function to print contents of
// a vector from index i to it's end
void printvector(const vector& v, int i)
{
for (int j = i; j < v.size(); j )
cout << v[j] << " ";
cout << endl;
}
// binary tree node
struct node {
int data;
node *left, *right;
node(int x)
{
data = x;
left = right = null;
}
};
// this function prints all paths that have sum k
void printkpathutil(node* root, vector& path, int k)
{
// empty node
if (!root)
return;
// add current node to the path
path.push_back(root->data);
// check if there's any k sum path
// in the left sub-tree.
printkpathutil(root->left, path, k);
// check if there's any k sum path
// in the right sub-tree.
printkpathutil(root->right, path, k);
// check if there's any k sum path that
// terminates at this node
// traverse the entire path as
// there can be negative elements too
int f = 0;
for (int j = path.size() - 1; j >= 0; j--) {
f = path[j];
// if path sum is k, print the path
if (f == k)
printvector(path, j);
}
// remove the current element from the path
path.pop_back();
}
// a wrapper over printkpathutil()
void printkpath(node* root, int k)
{
vector path;
printkpathutil(root, path, k);
}
// driver code
int main()
{
node* root = new node(1);
root->left = new node(3);
root->left->left = new node(2);
root->left->right = new node(1);
root->left->right->left = new node(1);
root->right = new node(-1);
root->right->left = new node(4);
root->right->left->left = new node(1);
root->right->left->right = new node(2);
root->right->right = new node(5);
root->right->right->right = new node(2);
int k = 5;
printkpath(root, k);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print all paths with sum k.
import java.util.*;
class gfg {
// utility function to print contents of
// a vector from index i to it's end
static void printvector(vector v, int i)
{
for (int j = i; j < v.size(); j )
system.out.print(v.get(j) " ");
system.out.println();
}
// binary tree node
static class node {
int data;
node left, right;
node(int x)
{
data = x;
left = right = null;
}
};
static vector path = new vector();
// this function prints all paths that have sum k
static void printkpathutil(node root, int k)
{
// empty node
if (root == null)
return;
// add current node to the path
path.add(root.data);
// check if there's any k sum path
// in the left sub-tree.
printkpathutil(root.left, k);
// check if there's any k sum path
// in the right sub-tree.
printkpathutil(root.right, k);
// check if there's any k sum path that
// terminates at this node
// traverse the entire path as
// there can be negative elements too
int f = 0;
for (int j = path.size() - 1; j >= 0; j--) {
f = path.get(j);
// if path sum is k, print the path
if (f == k)
printvector(path, j);
}
// remove the current element from the path
path.remove(path.size() - 1);
}
// a wrapper over printkpathutil()
static void printkpath(node root, int k)
{
path = new vector();
printkpathutil(root, k);
}
// driver code
public static void main(string args[])
{
node root = new node(1);
root.left = new node(3);
root.left.left = new node(2);
root.left.right = new node(1);
root.left.right.left = new node(1);
root.right = new node(-1);
root.right.left = new node(4);
root.right.left.left = new node(1);
root.right.left.right = new node(2);
root.right.right = new node(5);
root.right.right.right = new node(2);
int k = 5;
printkpath(root, k);
}
}
// this code is contributed by arnab kundu
python 3
# python3 program to print all paths
# with sum k
# utility function to print contents of
# a vector from index i to it's end
def printvector(v, i):
for j in range(i, len(v)):
print(v[j], end=" ")
print()
# binary tree node
""" utility that allocates a newnode
with the given key """
class newnode:
# construct to create a newnode
def __init__(self, key):
self.data = key
self.left = none
self.right = none
# this function prints all paths
# that have sum k
def printkpathutil(root, path, k):
# empty node
if (not root):
return
# add current node to the path
path.append(root.data)
# check if there's any k sum path
# in the left sub-tree.
printkpathutil(root.left, path, k)
# check if there's any k sum path
# in the right sub-tree.
printkpathutil(root.right, path, k)
# check if there's any k sum path that
# terminates at this node
# traverse the entire path as
# there can be negative elements too
f = 0
for j in range(len(path) - 1, -1, -1):
f = path[j]
# if path sum is k, print the path
if (f == k):
printvector(path, j)
# remove the current element
# from the path
path.pop(-1)
# a wrapper over printkpathutil()
def printkpath(root, k):
path = []
printkpathutil(root, path, k)
# driver code
if __name__ == '__main__':
root = newnode(1)
root.left = newnode(3)
root.left.left = newnode(2)
root.left.right = newnode(1)
root.left.right.left = newnode(1)
root.right = newnode(-1)
root.right.left = newnode(4)
root.right.left.left = newnode(1)
root.right.left.right = newnode(2)
root.right.right = newnode(5)
root.right.right.right = newnode(2)
k = 5
printkpath(root, k)
# this code is contributed by
# shubham singh(shubhamsingh10)
c
// c# program to print all paths with sum k.
using system;
using system.collections.generic;
class gfg {
// utility function to print contents of
// a vector from index i to it's end
static void printlist(list v, int i)
{
for (int j = i; j < v.count; j )
console.write(v[j] " ");
console.writeline();
}
// binary tree node
public class node {
public int data;
public node left, right;
public node(int x)
{
data = x;
left = right = null;
}
};
static list path = new list();
// this function prints all paths that have sum k
static void printkpathutil(node root, int k)
{
// empty node
if (root == null)
return;
// add current node to the path
path.add(root.data);
// check if there's any k sum path
// in the left sub-tree.
printkpathutil(root.left, k);
// check if there's any k sum path
// in the right sub-tree.
printkpathutil(root.right, k);
// check if there's any k sum path that
// terminates at this node
// traverse the entire path as
// there can be negative elements too
int f = 0;
for (int j = path.count - 1; j >= 0; j--) {
f = path[j];
// if path sum is k, print the path
if (f == k)
printlist(path, j);
}
// remove the current element from the path
path.removeat(path.count - 1);
}
// a wrapper over printkpathutil()
static void printkpath(node root, int k)
{
path = new list();
printkpathutil(root, k);
}
// driver code
public static void main(string[] args)
{
node root = new node(1);
root.left = new node(3);
root.left.left = new node(2);
root.left.right = new node(1);
root.left.right.left = new node(1);
root.right = new node(-1);
root.right.left = new node(4);
root.right.left.left = new node(1);
root.right.left.right = new node(2);
root.right.right = new node(5);
root.right.right.right = new node(2);
int k = 5;
printkpath(root, k);
}
}
// this code is contributed by princiraj1992
java 描述语言
// tree node class for binary tree
// representation
class node {
constructor(data) {
this.data = data;
this.left = this.right = null;
}
}
function printpathutil(node, k, path_arr, all_path_arr) {
if (node == null) {
return;
}
let p1 = node.data.tostring();
let p2 = '';
if (path_arr.length > 0) {
p2 = path_arr ',' p1;
}
else {
p2 = p1;
}
if (node.data == k) {
all_path_arr.add(p1);
}
let sum = 0;
let p2_arr = p2.split(',');
for (let i = 0; i < p2_arr.length; i ) {
sum = sum number(p2_arr[i]);
}
if (sum == k) {
all_path_arr.add(p2);
}
printpathutil(node.left, k, p1, all_path_arr)
printpathutil(node.left, k, p2, all_path_arr)
printpathutil(node.right, k, p1, all_path_arr)
printpathutil(node.right, k, p2, all_path_arr)
}
function printkpath(root, k) {
let all_path_arr = new set();
printpathutil(root, k, '', all_path_arr);
return all_path_arr;
}
function printpaths(paths) {
for (let data of paths) {
document.write(data.replaceall(',', ' '));
document.write('
');
}
}
// driver code
let root = new node(1);
root.left = new node(3);
root.left.left = new node(2);
root.left.right = new node(1);
root.left.right.left = new node(1);
root.right = new node(-1);
root.right.left = new node(4);
root.right.left.left = new node(1);
root.right.left.right = new node(2);
root.right.right = new node(5);
root.right.right.right = new node(2);
let k = 5;
printpaths(printkpath(root, k));
// this code is contributed by gaurav2146
输出:
3 2
3 1 1
1 3 1
4 1
1 -1 4 1
-1 4 2
5
1 -1 5
时间复杂度:o(nhh) ，因为路径向量的最大大小可以是 h
空间复杂度:o(h)
？list = plqm7 alhxfyshcxd 7 r1j 0k y9 zg _ gbb1 dbk 本文由 投稿如果你喜欢 geeksforgeeks 并愿意投稿，也可以使用写一篇文章或者将文章邮寄到 review-team@geeksforgeeks.org。看到你的文章出现在极客博客pg电子试玩链接主页上，帮助其他极客。 如果发现有不正确的地方，或者想分享更多关于上述话题的信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
