{10,5,12,4,7},22[[10,5,7],[10,12]]
返回[[10,12],[10,5,7]]也是对的
{10,5,12,4,7},15[]
{2,3},0[]
{1,3,4},7[]
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;
}
};
/*
非递归法：后序遍历
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;
}
};
# -*- 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
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;
list.add(root.val);
target -= root.val;
if(target == 0 && root.left == null && root.right == null)
listAll.add(new ArrayList<Integer>(list));
FindPath(root.left, target);
FindPath(root.right, target);
list.remove(list.size()-1);
return listAll;
}
}
//非递归版本
//思路：
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;
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){
list.add(new Integer(i));
}
list.add(new Integer(root.val));
pathList.add(list);
}
}
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
path.add(root.val);
//已经到达叶子节点，并且正好加出了target
if (root.val == target && root.left == null && root.right == null) {
//将该路径加入res结果集中
res.add(new ArrayList(path));
}
//如果左子树非空，递归左子树
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;
}
}
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;
list.add(root.val);
target -= root.val;
if(target == 0 && root.left == null && root.right == null) {
res.add(new ArrayList<Integer>(list));
}
FindPath(root.left, target);
FindPath(root.right, target);
list.remove(list.size() - 1);
return res;
}
}
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 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
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;
}
};
注意两点：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;
}
};
class Solution {
public:
vector<vector<int> > ans;
vector<int> v;
void solve(TreeNode* node, int res){
v.push_back(node->val);
if(res - node->val == 0 && !node->left && !node->right)
ans.push_back(v);
else{
if(node->left) solve(node->left, res - node->val);
if(node->right) solve(node->right, res - node->val);
}
v.pop_back();
}
vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {
if(root) solve(root, expectNumber);
return ans;
}
};
# -*- 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 
非递归实现 ，出栈是后序遍历
private ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
Stack<TreeNode> stack = new Stack<TreeNode>();
HashMap<TreeNode, Boolean> rightDealed = new HashMap<>();
TreeNode node = root;
while (node != null || stack.size() > 0) {
if (node != null) {
stack.push(node);
System.out.println("push:" + node.val);//先序
addPath(node,stack,target);
node = node.left;
} else {
node = stack.peek();
if (rightDealed.get(node) != null) {//已访问过右节点 该出栈了
stack.pop();
System.out.println("pop:" + node.val);//后序
node=null;
}else{ //若未访问右节点先不出栈
rightDealed.put(node, true);
node = node.right;
}
}
}
return listAll;
}
public void addPath(TreeNode node,Stack<TreeNode> stack,int target){
if(node.left==null&&node.right==null){
ArrayList<Integer> list=new ArrayList();
int total=0;
for (TreeNode treeNode : stack) {
list.add(treeNode.val);
total=total+treeNode.val;
System.out.print(treeNode.val + " ");
}
if(total==target){
listAll.add(list);
}
}
}
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;
list1.add(root.val);
if(target-root.val==0 && root.left==null && root.right==null){
list.add(new ArrayList<Integer> (list1));
}
getPath(root.left, target-root.val, list1);
getPath(root.right, target-root.val, list1);
list1.remove(list1.size()-1);
}
}
# 后序遍历，只有在叶子结点计算完毕符合要求的路径才会返回路径的节点列表，否则返回空列表
def FindPath(self, root, expectNumber):
# write code here
if not root: # 输入为空树时，返回空列表
return []
if not root.left and not root.right: # 到达叶子结点
return [[root.val,],] if root.val == expectNumber else [] # 如果叶子结点的值符合最后需要的那一个值，需要返回该路径，否则返回空列表
if root.val < expectNumber: # 非叶子节点时，如果当前节点值小于需要值，则继续遍历
x = self.FindPath(root.left,expectNumber-root.val) + self.FindPath(root.right,expectNumber-root.val) # 遍历结果为左右子树遍历结果的集合
return sorted([[root.val,]+each for each in x],key=lambda x:len(x),reverse=True)if x else [] # 如果有结果则加上本节点并且对结果长度依次排序，否则返回空列表
else: # 非叶子节点时，如果当前节点值已经超过需要的数，则提前结束该分支的遍历
return []
public class Solution {
private ArrayList<ArrayList<Integer>> res;
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
res = new ArrayList<>();
backtrack(root, target, new ArrayList<Integer>());
return res;
}
private void backtrack(TreeNode root, int target, ArrayList<Integer> ls) {
//终止条件
if(root == null) return;
//修正target
target -= root.val;
//添加进list
ls.add(root.val);
//判断是否满足要求
if(target == 0 && root.left == null && root.right == null) {
//将当前的ls加入到结果
res.add(new ArrayList<Integer>(ls));
}
//递归
backtrack(root.left, target, ls);
backtrack(root.right, target, ls);
//删除不满足要求的
ls.remove(ls.size() - 1);
}
} 
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;
}
ArrayList<Integer> path = new ArrayList<Integer>();
findPaths(root, target, path, paths);
return paths;
}
public void findPaths(TreeNode root, int target, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> paths){
path.add(root.val);
if (target == root.val && root.left == null && root.right == null) {
paths.add(path);
return;
}
ArrayList<Integer> path2 = new ArrayList<Integer>();
path2.addAll(path);
if (root.left != null) {
findPaths(root.left, target - root.val, path, paths);
}
if (root.right != null) {
findPaths(root.right, target - root.val, path2, paths);
}
}
}
import java.util.ArrayList;
public class Solution {
private ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root == null || target == 0) return ret;
backtracing(root,target,new ArrayList<>());
return ret;
}
public void backtracing(TreeNode root , int target, ArrayList<Integer> path){
//1.递归终止条件
//到达叶子的左右子树（空）时返回
if(root == null)
return;
//2.当前层要做的事情
path.add(root.val);
target -= root.val;
//如果当前层是叶子节点且路径找对了，添加到ret里
if(target == 0 && root.left == null && root.right == null)
ret.add(new ArrayList<>(path));
//3.不满足条件就下沉drill down
else{
backtracing(root.left,target,path);
backtracing(root.right,target,path);
}
//4.恢复当前层被递归破坏的状态
path.remove(path.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;
}
};
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
