首页 > 试题广场 > 二叉树中和为某一值的路径
[编程题]二叉树中和为某一值的路径
输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中,数组长度大的数组靠前)

886个回答

添加回答
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;
    }
}

编辑于 2016-03-05 18:26:19 回复(263)
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;
    }
};

编辑于 2015-09-13 18:38:39 回复(61)
这类问题可以用带记忆的DFS来解决。分享一个这类问题的典型解法。
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();
    }
};

发表于 2016-07-15 12:32:01 回复(25)
思路: 
  •      递归先序遍历树, 把结点加入路径。
  •      若该结点是叶子结点则比较当前路径和是否等于期待和。
  •     弹出结点,每一轮递归返回到父结点时,当前路径也应该回退一个结点
# -*- 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

发表于 2016-07-25 16:24:46 回复(9)
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;
	}
};

发表于 2016-08-01 11:41:49 回复(22)
//非递归版本
//思路:
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;
}

编辑于 2015-09-11 19:51:01 回复(23)
这个还是比较简单的,经典的递归策略。
提供一个Java版本的:
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){
        path.add(root.val);
        if(root.left==null&&root.right==null){
            if(target==root.val){
                paths.add(path);
            }
            return;
        }
        ArrayList<Integer> path2=new ArrayList<>();
        path2.addAll(path);
        if(root.left!=null)find(paths,path,root.left,target-root.val);
        if(root.right!=null)find(paths,path2,root.right,target-root.val);
    }
}

发表于 2016-04-20 17:18:03 回复(21)
/*
非递归法:后序遍历
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;
	}
};

编辑于 2017-09-05 16:39:22 回复(4)
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();
        }
        
    }
}


发表于 2015-04-22 23:58:11 回复(19)
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;
    }
    
}

发表于 2018-03-26 14:50:10 回复(5)
让一让让一让,python大法来了~
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

发表于 2018-07-01 14:06:29 回复(8)
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;
    }
};

发表于 2015-08-28 23:13:55 回复(5)

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
编辑于 2019-03-11 22:40:26 回复(6)
# -*- 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

发表于 2018-02-10 10:46:38 回复(7)
注意两点: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;
    }
};

编辑于 2017-05-05 15:19:03 回复(1)
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;
	}
}

发表于 2017-04-21 17:47:05 回复(4)
测试用例不全面!!!
这道题题目中要求 (注意: 在返回值的list中,数组长度大的数组靠前)
应该将最后生成的list中的各个数组按照数组的长度由大到小排序,因为在递归方法中list中数组的添加顺序并不能保证一定是长度最长的先添加进list !
如果不考虑这点,测试是可以通过的!所以测试用例是不全面的。以下是我的java代码:

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;
        cur.add(value);
        if (target==value&&root.left==null&&root.right==null){
            res.add(new ArrayList<>(cur));
        }else {
            helper(root.left,target-value,cur,res);
            helper(root.right,target-value,cur,res);
        }

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

编辑于 2018-10-02 00:17:27 回复(4)
按照回溯法的套路来搞
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);
    }
}

编辑于 2018-03-27 16:10:07 回复(4)
/* 思路更为清晰的递归方式 -- 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;
    }
};

发表于 2017-04-10 23:13:59 回复(2)
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;
    }
};
发表于 2018-12-04 21:45:26 回复(0)