[编程题]二叉树中和为某一值的路径

# 819个回答

```public class Solution {
private ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();
private ArrayList<Integer> list = new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root == null) return listAll;
target -= root.val;
if(target == 0 && root.left == null && root.right == null)
FindPath(root.left, target);
FindPath(root.right, target);
list.remove(list.size()-1);
return listAll;
}
}```

```class Solution {
vector<vector<int> >allRes;
vector<int> tmp;
void dfsFind(TreeNode * node , int left){
tmp.push_back(node->val);
if(left-node->val == 0 && !node->left && !node->right)
allRes.push_back(tmp);
else {
if(node->left) dfsFind(node->left, left-node->val);
if(node->right) dfsFind(node->right, left-node->val);
}
tmp.pop_back();
}
public:
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
if(root) dfsFind(root, expectNumber);
return allRes;
}
};```

```class Solution {
public:
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
vector<vector<int>> ret;
vector<int> trace;
if(root)
dfs(root,expectNumber,ret,trace);
return ret;
}
void dfs(TreeNode* root,int s,vector<vector<int>> &ret,vector<int> &trace) {
trace.push_back(root->val);
if(!root->left&&!root->right) {
if(s==root->val)
ret.push_back(trace);
}
if(root->left)
dfs(root->left,s-root->val,ret,trace);
if(root->right)
dfs(root->right,s-root->val,ret,trace);
trace.pop_back();
}
};```

•      递归先序遍历树， 把结点加入路径。
•      若该结点是叶子结点则比较当前路径和是否等于期待和。
•     弹出结点，每一轮递归返回到父结点时，当前路径也应该回退一个结点
```# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
# 返回二维列表，内部每个列表表示找到的路径
def FindPath(self, root, expectNumber):
# write code here
if not root:
return []

result = []

def FindPathMain(root, path, currentSum):
currentSum += root.val

path.append(root)
isLeaf = root.left == None and root.right == None

if currentSum == expectNumber and isLeaf:
onePath = []
for node in path:
onePath.append(node.val)
result.append(onePath)

if currentSum < expectNumber:
if root.left:
FindPathMain(root.left, path, currentSum)
if root.right:
FindPathMain(root.right, path, currentSum)

path.pop()

FindPathMain(root, [], 0)

return result```

```class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void find(TreeNode* root,  int sum)
{
if (root == NULL)return;
path.push_back(root->val);
if (!root->left && !root->right && sum == root->val)
res.push_back(path);
else
{
if (root->left)
find(root->left, sum - root->val);
if (root->right)
find(root->right, sum - root->val);
}
path.pop_back();
}
vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
find(root, expectNumber);
return res;
}
};```

```//非递归版本
//思路：
1.按先序遍历把当前节点cur的左孩子依次入栈同时保存当前节点，每次更新当前路径的和sum；
2.判断当前节点是否是叶子节点以及sum是否等于expectNumber，如果是，把当前路径放入结果中。
3.遇到叶子节点cur更新为NULL，此时看栈顶元素，如果栈顶元素的把栈顶元素保存在last变量中，同时弹出栈顶元素，当期路径中栈顶元素弹出，sum减掉栈顶元素，这一步骤不更改cur的值；
4.如果步骤3中的栈顶元素的右孩子存在且右孩子之前没有遍历过，当前节点cur更新为栈顶的右孩子，此时改变cur=NULL的情况。

#include <iostream>
#include <vector>

using namespace std;

struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL){}
}

vector<vector<int> > FindPath(TreeNode *root, int expectNumber){
vector<vector<int> > res;
if (root == NULL)
return res;
stack<TreeNode *> s;
s.push(root);
int sum = 0; //当前和
vector<int> curPath; //当前路径
TreeNode *cur = root; //当前节点
TreeNode *last = NULL; //保存上一个节点
while (!s.empty()){
if (cur == NULL){
TreeNode *temp = s.top();
if (temp->right != NULL && temp->right != last){
cur = temp->right; //转向未遍历过的右子树
}else{
last = temp; //保存上一个已遍历的节点
s.pop();
curPath.pop_back(); //从当前路径删除
sum -= temp->val;
}  }
else{
s.push(cur);
sum += cur->val;
curPath.push_back(cur->val);
if (cur->left == NULL && cur->right == NULL && sum == expectNum){
res.push_back(curPath);
}
cur = cur->left; //先序遍历，左子树先于右子树
}
}
return res;
}```

```import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;

}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
ArrayList<ArrayList<Integer>> paths=new ArrayList<ArrayList<Integer>>();
if(root==null)return paths;
find(paths,new ArrayList<Integer>(),root,target);
return paths;
}
public void find(ArrayList<ArrayList<Integer>> paths,ArrayList<Integer> path,TreeNode root,int target){
if(root.left==null&&root.right==null){
if(target==root.val){
}
return;
}
ArrayList<Integer> path2=new ArrayList<>();
if(root.left!=null)find(paths,path,root.left,target-root.val);
if(root.right!=null)find(paths,path2,root.right,target-root.val);
}
}```

```import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,
int target) {
ArrayList<ArrayList<Integer>> pathList=
new ArrayList<ArrayList<Integer>>();
if(root==null)
return pathList;
Stack<Integer> stack=new Stack<Integer>();
FindPath(root,target,stack,pathList );
return pathList;

}
private void FindPath(TreeNode root, int target,
Stack<Integer> path,
ArrayList<ArrayList<Integer>> pathList) {
if(root==null)
return;
if(root.left==null&&root.right==null){
if(root.val==target){
ArrayList<Integer> list=
new ArrayList<Integer>();
for(int i:path){
}
}
}
else{
path.push(new Integer(root.val));
FindPath(root.left, target-root.val, path, pathList);
FindPath(root.right, target-root.val, path,  pathList);
path.pop();
}

}
}

```

```public class Solution {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
ArrayList<Integer> path = new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if (root == null) {
return res;
}
findPath(root, target);
return res;
}

public void findPath(TreeNode root, int target) {
//因为FindPath中和 下面程序中都进行了判null操作，root绝对不可能为 null
//已经到达叶子节点，并且正好加出了target
if (root.val == target && root.left == null && root.right == null) {
//将该路径加入res结果集中
}
//如果左子树非空，递归左子树
if (root.left != null) {
findPath(root.left, target - root.val);
}
//如果右子树非空，递归右子树
if (root.right != null) {
findPath(root.right, target - root.val);
}
//无论当前路径是否加出了target，必须去掉最后一个，然后返回父节点，去查找另一条路径，最终的path肯定为null
path.remove(path.size() - 1);
return;
}

}
```

```/*

1.进栈时候，把值同时压入路径的向量数组，修正路径的和
2.出栈时候，先判断和是否相等，且该节点是否是叶节点，

3.向量数组和栈的操作要保持一致
*/
class Solution {
public:
vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {
stack<TreeNode*> s;
vector<int> v;
vector<vector<int> > res;
while (root || !s.empty()){
while (root){
s.push(root); v.push_back(root->val); expectNumber -= root->val;
//能左就左，否则向右
root = root->left ? root->left : root->right;
}
root = s.top();
if (expectNumber == 0 && root->left == NULL && root->right == NULL)
res.push_back(v);
s.pop(); v.pop_back(); expectNumber += root->val;
//右子数没遍历就遍历，如果遍历就强迫出栈
if (!s.empty() && s.top()->left == root)
root = s.top()->right;
else
root = NULL;//强迫出栈
}
return res;
}
};
```

```class Solution {
void TreePath(TreeNode* root,int target,vector<int> &path,vector<vector<int> > &pathList)
{
if(root == NULL)
return ;
path.push_back(root->val);
bool isLeaf = root->left==NULL && root->right==NULL;
if(root->val==target && isLeaf)
{
pathList.push_back(path);
path.pop_back();
}
else
{
TreePath(root->left,target - root->val,path,pathList);
TreePath(root->right,target - root->val,path,pathList);
path.pop_back();
}
}
public:
vector<vector<int> > FindPath(TreeNode* root,int expectNumber)
{
vector<vector<int> > FindPath;
vector<int> Path;  // 为了保存每一次递归的值,这里声明了一个path
if(root == NULL)
return FindPath;
TreePath(root,expectNumber,Path,FindPath);
return FindPath;
}
};
```

```class Solution:
def FindPath(self, root, expectNumber):
def subFindPath(root):
if root:
b.append(root.val)
if not root.right and not root.left and sum(b) == expectNumber:
a.append(b[:])
else:
subFindPath(root.left),subFindPath(root.right)
b.pop()
a, b = [], []
subFindPath(root)
return a
```

```# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
def __init__(self):

self.list = []
self.list1 = []
def FindPath(self, root, expectNumber):
if root == None:
return self.list1
# print('********')
self.list.append(root.val)
# print(list)
expectNumber -= root.val
# print('----', target)
if expectNumber == 0 and root.left == None and root.right == None:
newlist = []
for line in self.list:
newlist.append(line)
self.list1.append(newlist)
# print('*****', list1)
# list1.append(proot.val)
# print(list1)
# print(list)
# print('********')
# print(proot.val)
# print('********')

self.FindPath(root.left, expectNumber)

self.FindPath(root.right, expectNumber)
self.list.pop()
return self.list1```

```注意两点：1）每次遍历到一个node时，expectNumber -= node->val,这样，遍历到叶子时，只要判断expectNumber是否为0即可。
2）用vector<int>& tmp记录路径而不是用vector<int> tmp，后者占用大量空间时间。
使用前者只需要在每次递归调用返回时，pop_back()一下，就可以了。 public:
void HelperFunc(vector<vector<int> >& ret, vector<int>& tmp, TreeNode* node, int expectNumber){
tmp.push_back(node->val);
expectNumber -= node->val;
if(node->left==NULL && node->right==NULL){
if(expectNumber == 0)
ret.push_back(tmp);
}
if(node->left!=NULL){
HelperFunc(ret, tmp, node->left, expectNumber);
tmp.pop_back();
}
if(node->right!=NULL){
HelperFunc(ret, tmp, node->right, expectNumber);
tmp.pop_back();
}
}
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
vector<vector<int> > ret;
vector<int> tmp;
if(root!=NULL)
HelperFunc(ret, tmp, root, expectNumber);
return ret;
}
};```

```import java.util.ArrayList;
public class Solution {
private ArrayList<ArrayList<Integer>> res = new ArrayList<>();
private ArrayList<Integer> list = new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
if(root == null) return res;
target -= root.val;
if(target == 0 && root.left == null && root.right == null) {
}
FindPath(root.left, target);
FindPath(root.right, target);
list.remove(list.size() - 1);
return res;
}
}```

# python 解法：

```class Solution:
# 返回二维列表，内部每个列表表示找到的路径
def FindPath(self, root, expectNumber):
res=[]
treepath=self.dfs(root)
for i in treepath:
if sum(map(int,i.split('->')))==expectNumber:
res.append(list(map(int,i.split('->'))))
return res

def dfs(self, root):
if not root: return []
if not root.left and not root.right:
return [str(root.val)]
treePath = [str(root.val) + "->" + path for path in self.dfs(root.left)]
treePath += [str(root.val) + "->" + path for path in self.dfs(root.right)]
return treePath```

## 9行：

```class Solution:
def FindPath(self, root, expectNumber):
return [map(int, i.split("->")) for i in self.dfs(root) if sum(map(int, i.split('->'))) == expectNumber]
def dfs(self, root):
if not root: return []
if not root.left and not root.right: return [str(root.val)]
treePath = [str(root.val) + "->" + path for path in self.dfs(root.left)]
treePath += [str(root.val) + "->" + path for path in self.dfs(root.right)]
return treePath```

```import java.util.*;

public class Solution {
ArrayList<ArrayList<Integer>> list=new ArrayList<ArrayList<Integer>>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
ArrayList<Integer> list1=new ArrayList<>();
getPath(root, target, list1);
return list;
}

public void getPath(TreeNode root, int target, ArrayList<Integer> list1){
if(root==null|| target<0) return;
if(target-root.val==0 && root.left==null && root.right==null){
}
getPath(root.left, target-root.val, list1);
getPath(root.right, target-root.val, list1);
list1.remove(list1.size()-1);
}
}
```

```public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
ArrayList<ArrayList<Integer>> res=new ArrayList<>();
ArrayList<Integer> cur=new ArrayList<>();

helper(root,target,cur,res);
Collections.sort(res, new Comparator<ArrayList<Integer>>() {
@Override
public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
if (o1.size()<o2.size()){
return 1;
}else return -1;
}
});
return res;
}
public void helper(TreeNode root,int target,ArrayList<Integer> cur,ArrayList<ArrayList<Integer>> res){
if (root==null) return;
int value=root.val;
if (target==value&&root.left==null&&root.right==null){
}else {
helper(root.left,target-value,cur,res);
helper(root.right,target-value,cur,res);
}

cur.remove(cur.size()-1);
}
```

```/* 思路更为清晰的递归方式 -- path与ret均定义在函数内部 */
/* 递归方式 */
class Solution {
void DFSFindPath(TreeNode* root, int rest, vector<vector<int>> &path, vector<int> &ret)
{
rest -= root->val;  // 减去当前结点的值
ret.push_back(root->val);

// 如果是叶子结点，则看此时路径和是否等于exceptNumber，是则保留该路径
if(root->left == nullptr && root->right == nullptr)
if(rest == 0) path.push_back(ret);

// 如果不是叶子结点，若rest != 0,则递归进入左右子树（注：若rest==0，则删除该结点后返回）
if( rest != 0 && root->left != nullptr)
DFSFindPath(root->left,rest,path,ret);
if( rest != 0 && root->right != nullptr)
DFSFindPath(root->right,rest,path,ret);

ret.pop_back();   // 退出该结点前，在路径中删除该结点
}
public:
vector<vector<int> > FindPath(TreeNode* root,int expectNumber)
{
vector<vector<int>> path;
vector<int> ret;
if(root != nullptr)
DFSFindPath(root,expectNumber,path,ret);

return path;
}
};```

```# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
# 返回二维列表，内部每个列表表示找到的路径
def FindPath(self, root, expectNumber):
# write code here
#空树或根节点值大的情况直接返回
if not root or root.val>expectNumber:
return []
#叶子节点情况,注意需返回二维list
if not root.left and not root.right and root.val==expectNumber:
return [[root.val]]
else:
expectNumber -= root.val
#递归分别求左右子树中的路径
left = self.FindPath(root.left, expectNumber)
right = self.FindPath(root.right, expectNumber)
#与根节点合并
result = [[root.val]+x for x in left]
for x in right:
result.append([root.val]+x)
#输出按路径长度排序的路径列表
return sorted(result, key=lambda x:-len(x))
```

819条回答 81948浏览

# 通过挑战的用户

• 2019-03-26 05:17:39
• 2019-03-26 04:05:37
• 2019-03-26 02:41:44
• 2019-03-26 02:06:24
• 2019-03-26 01:14:34

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题

• 公司地址：北京市朝阳区大屯路东金泉时代3-2708北京牛客科技有限公司