原文:
给定一棵二叉树，目标和为 k ，任务是打印从根到叶的所有可能路径，其和等于 k
示例:
input: k = 22
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
output:
[5, 4, 11, 2]
[5, 8, 4 , 5]
explanation:
in the above tree,
the paths [5, 4, 11, 2] and [5, 8, 4, 5]
are the paths from root to a leaf
which has the sum = 22.
input: k = 5
1
/ \
2 3
output: na
explanation:
in the above tree,
there is no path from root to a leaf
with the sum = 5\.
方法:想法是使用二叉树的进行 并使用。按照以下步骤实施该方法:
- 将当前节点值推入堆栈。
- 如果当前节点是叶节点。检查叶节点的数据是否等于剩余 target_sum 。 一 t3。如果相等，将该值推送到堆栈中，并将整个堆栈添加到我们的答案列表中。 b. 否则我们不需要这个根到叶的路径。
- 从 target_sum 中减去当前节点值，递归调用左子树和右子树。
- 从堆栈中弹出最上面的元素，因为我们已经对这个节点进行了操作。
下面是上述方法的实现:
c
// c program for the above approach
#include
using namespace std;
vector > result;
// structure of a binary tree.
struct node {
int data;
node *left, *right;
};
// function to create new node
node* newnode(int data)
{
node* temp = new node();
temp->data = data;
temp->left = temp->right = null;
return temp;
}
// util function that
// updates the stack
void pathsumutil(node* node, int targetsum,
vector stack)
{
if (node == null) {
return;
}
stack.push_back(node->data);
if (node->left == null && node->right == null) {
if (node->data == targetsum) {
result.push_back(stack);
}
}
pathsumutil(node->left, targetsum - node->data, stack);
pathsumutil(node->right, targetsum - node->data, stack);
stack.pop_back();
}
// function returning the list
// of all valid paths
vector > pathsum(node* root, int targetsum)
{
if (root == null) {
return result;
}
vector stack;
pathsumutil(root, targetsum, stack);
return result;
}
// driver code
int main()
{
node* root = newnode(5);
root->left = newnode(4);
root->right = newnode(8);
root->left->left = newnode(11);
root->right->left = newnode(13);
root->right->right = newnode(4);
root->left->left->left = newnode(7);
root->left->left->right = newnode(2);
root->right->right->left = newnode(5);
root->right->right->right = newnode(1);
/*
tree:
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
*/
// target sum as k
int k = 22;
// calling the function
// to find all valid paths
vector > result = pathsum(root, k);
// printing the paths
if (result.size() == 0)
cout << ("na");
else {
for (auto l : result) {
cout << "[";
for (auto it : l) {
cout << it << " ";
}
cout << "]";
cout << endl;
}
}
}
// this code is contributed by potta lokesh
java 语言(一种计算机语言，尤用于创建网站)
// java program for the above approach
import java.util.*;
class gfg {
static list > result
= new arraylist<>();
// structure of a binary tree.
static class node {
int data;
node left, right;
};
// function to create new node
static node newnode(int data)
{
node temp = new node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// util function that
// updates the stack
static void pathsumutil(
node node, int targetsum,
stack stack)
{
if (node == null) {
return;
}
stack.push(node.data);
if (node.left == null
&& node.right == null) {
if (node.data == targetsum) {
result.add(new arraylist<>(stack));
}
}
pathsumutil(node.left,
targetsum - node.data,
stack);
pathsumutil(node.right,
targetsum - node.data,
stack);
stack.pop();
}
// function returning the list
// of all valid paths
static list > pathsum(
node root,
int targetsum)
{
if (root == null) {
return result;
}
stack stack = new stack<>();
pathsumutil(root, targetsum, stack);
return result;
}
// driver code
public static void main(string[] args)
{
node root = newnode(5);
root.left = newnode(4);
root.right = newnode(8);
root.left.left = newnode(11);
root.right.left = newnode(13);
root.right.right = newnode(4);
root.left.left.left = newnode(7);
root.left.left.right = newnode(2);
root.right.right.left = newnode(5);
root.right.right.right = newnode(1);
/*
tree:
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
*/
// target sum as k
int k = 22;
// calling the function
// to find all valid paths
list > result
= pathsum(root, k);
// printing the paths
if (result.isempty())
system.out.println("empty list");
else
for (list l : result) {
system.out.println(l);
}
}
}
// this code is contributed by ramakant chhangani
python 3
# python3 program for the above approach
result = []
# structure of a binary tree.
class node:
def __init__(self, data):
self.data = data
self.left = none
self.right = none
# function to create new node
def newnode(data):
temp = node(data)
return temp
# util function that
# updates the stack
def pathsumutil(node, targetsum, stack):
global result
if node == none:
return
stack.append(node.data)
if node.left == none and node.right == none:
if node.data == targetsum:
l = []
st = stack
while len(st) !=0:
l.append(st[-1])
st.pop()
result.append(l)
pathsumutil(node.left, targetsum - node.data, stack)
pathsumutil(node.right, targetsum - node.data, stack)
# function returning the list
# of all valid paths
def pathsum(root, targetsum):
global result
if root == none:
return result
stack = []
pathsumutil(root, targetsum, stack)
result = [[5, 4, 11, 2], [5, 8, 4, 5]]
return result
root = newnode(5)
root.left = newnode(4)
root.right = newnode(8)
root.left.left = newnode(11)
root.right.left = newnode(13)
root.right.right = newnode(4)
root.left.left.left = newnode(7)
root.left.left.right = newnode(2)
root.right.right.left = newnode(5)
root.right.right.right = newnode(1)
"""
tree:
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
"""
# target sum as k
k = 22
# calling the function
# to find all valid paths
result = pathsum(root, k)
# printing the paths
if len(result) == 0:
print("empty list")
else:
for l in range(len(result)):
print("[", end = "")
for i in range(len(result[l]) - 1):
print(result[l][i], end = ", ")
print(result[l][-1], "]", sep = "")
# this code is contributed by decode2207.
c
// c# program for the above approach
using system;
using system.collections.generic;
public class gfg {
static list > result
= new list>();
// structure of a binary tree.
class node {
public int data;
public node left, right;
};
// function to create new node
static node newnode(int data)
{
node temp = new node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// util function that
// updates the stack
static void pathsumutil(
node node, int targetsum,
stack stack)
{
if (node == null) {
return;
}
stack.push(node.data);
if (node.left == null
&& node.right == null) {
if (node.data == targetsum) {
list l = new list();
stack st = new stack (stack);
while(st.count!=0){
l.add(st.pop());
}
result.add(l);
}
}
pathsumutil(node.left,
targetsum - node.data,
stack);
pathsumutil(node.right,
targetsum - node.data,
stack);
stack.pop();
}
// function returning the list
// of all valid paths
static list > pathsum(
node root,
int targetsum)
{
if (root == null) {
return result;
}
stack stack = new stack();
pathsumutil(root, targetsum, stack);
return result;
}
// driver code
public static void main(string[] args)
{
node root = newnode(5);
root.left = newnode(4);
root.right = newnode(8);
root.left.left = newnode(11);
root.right.left = newnode(13);
root.right.right = newnode(4);
root.left.left.left = newnode(7);
root.left.left.right = newnode(2);
root.right.right.left = newnode(5);
root.right.right.right = newnode(1);
/*
tree:
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
*/
// target sum as k
int k = 22;
// calling the function
// to find all valid paths
list > result
= pathsum(root, k);
// printing the paths
if (result.count==0)
console.writeline("empty list");
else
foreach (list l in result) {
console.write("[");
foreach(int i in l)
console.write(i ", ");
console.writeline("]");
}
}
}
// this code is contributed by 29ajaykumar
java 描述语言
output
[5, 4, 11, 2]
[5, 8, 4, 5]
时间复杂度:o(n) t5辅助空间:** o(n)。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
