首页 > 试题广场 >

二叉树中和为某一值的路径(二)

[编程题]二叉树中和为某一值的路径(二)
  • 热度指数:781746 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
输入一颗二叉树的根节点root和一个整数expectNumber,找出二叉树中结点值的和为expectNumber的所有路径。
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点,不能从子节点到父节点
4.总节点数目为n

如二叉树root为{10,5,12,4,7},expectNumber为22
则合法路径有[[10,5,7],[10,12]]

数据范围:
树中节点总数在范围 [0, 5000] 内
-1000 <= 节点值 <= 1000
-1000 <= expectNumber <= 1000
示例1

输入

{10,5,12,4,7},22

输出

[[10,5,7],[10,12]]

说明

返回[[10,12],[10,5,7]]也是对的      
示例2

输入

{10,5,12,4,7},15

输出

[]
示例3

输入

{2,3},0

输出

[]
示例4

输入

{1,3,4},7

输出

[]

说明:本题目包含复杂数据结构TreeNode,点此查看相关信息
public class Solution {
	ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> arrayList = new ArrayList<>(); 
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
    	   
    	return way(root, 0, target);
    }
    private ArrayList<ArrayList<Integer>> way(TreeNode node,int way,int target) {//way表示到此节点的路径长度。    	
    	if(node==null)return list;
    	arrayList.add(node.val);    
    	way = way + node.val;
    	if(node.left!=null) {
    		way(node.left,way,target);
            arrayList.remove(arrayList.size()-1);//到达叶子节点,回到父节点。
    	}
    	if(node.right!=null) {
    		way(node.right,way,target);
    		arrayList.remove(arrayList.size()-1);
    	}
		if(node.left==null&&node.right==null&&way==target) {
			list.add(new ArrayList<Integer>(arrayList));//满足条件的ArrayList动态生成新。
			
		}
		return list;
	}
}

发表于 2019-09-02 00:13:32 回复(0)
更多回答
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 回复(73)
/*
非递归法:后序遍历
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)
思路: 
  •      递归先序遍历树, 把结点加入路径。
  •      若该结点是叶子结点则比较当前路径和是否等于期待和。
  •     弹出结点,每一轮递归返回到父结点时,当前路径也应该回退一个结点
# -*- 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 回复(17)
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 回复(367)
//非递归版本
//思路:
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 回复(24)
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 回复(8)
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 回复(6)

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)
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)
注意两点: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)
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 回复(1)
# -*- 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 回复(8)
非递归实现 ,出栈是后序遍历
 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);
            }
        }
    }

编辑于 2018-08-24 16:55:20 回复(1)
按照回溯法的套路来搞
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)
    # 后序遍历,只有在叶子结点计算完毕符合要求的路径才会返回路径的节点列表,否则返回空列表
    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 []
发表于 2019-06-13 18:48:01 回复(1)
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);
    }
}

发表于 2021-06-01 09:41:48 回复(0)

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);
        }
    }
   
}

发表于 2018-07-13 23:48:41 回复(1)

递归四部曲

  1. 递归终止条件
  2. 当前层要做的事情
  3. 下沉到下一层
  4. 恢复当前层的状态(if needed)
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);
    }
}
发表于 2019-04-09 09:20:21 回复(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;
    }
};

发表于 2017-04-10 23:13:59 回复(2)