首页 > 试题广场 >

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

[编程题]二叉树中和为某一值的路径(二)
  • 热度指数：781778 时间限制：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，点此查看相关信息
算法知识视频讲解
添加回答
Java
牛客581130865号头像 牛客581130865号 
public ArrayList<ArrayList<Integer>> FindPath (TreeNode root, int target) {
        // write code here
        if(root == null){
            return lists;
        }

        // 深度优先遍历/前序遍历
        list.add(root.val);

        //如果当前节点是叶子节点且满足题意，则保存list并返回
        if(root.left == null && root.right == null && root.val == target){
            lists.add(new ArrayList<Integer>(list));
            list.remove(list.indexOf(root.val));        //回溯
            return lists;
        }

        FindPath(root.left, target - root.val);
        FindPath(root.right, target - root.val);
        list.remove(list.indexOf(root.val));        //回溯

        return lists;
    }

发表于 2023-10-31 23:21:38 回复(0)
Java
VXTW头像 VXTW
终于过了 
import java.util.ArrayList;
import java.util.LinkedList;


public class Solution {
    LinkedList path = new LinkedList();
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        if (root == null) return res;
        path.add(root.val);
        target -= root.val;
        if (root.left == null && root.right == null && target == 0) {
            res.add(new ArrayList<>(path));
            return res;
        }
        if (root.left == null && root.right == null) {

            return res;
        }
        if (root.left != null) {
            FindPath(root.left, target);
            path.removeLast();
        }
      
        if (root.right != null) {
            FindPath(root.right, target);
            path.removeLast();
        }
       
        return res;
    }

}


发表于 2023-10-19 15:43:03 回复(0)
Java
腰马合一小垃圾头像 腰马合一小垃圾 
 public ArrayList<ArrayList<Integer>> FindPath (TreeNode root, int target) {
        // write code here
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        ArrayList<Integer> path = new ArrayList<>();
        process(root, path, target, ans);
        return ans;
    }

    private void process(TreeNode root, ArrayList<Integer> path, int target,ArrayList<ArrayList<Integer>> ans) {
        if (root.left == null && root.right == null) {
            if (target - root.val == 0) {
                path.add(root.val);
                ans.add(copyList(path));
                path.remove(path.size() - 1);
            }
            return;
        }

        path.add(root.val);
        if (root.left != null) {
            process(root.left, path, target - root.val, ans);
        }
        if (root.right != null) {
            process(root.right, path, target - root.val, ans);
        }
        path.remove(path.size() - 1);
    }

    private ArrayList<Integer> copyList(ArrayList<Integer> path) {
        ArrayList<Integer> copy = new ArrayList<>();
        for (int num : path) {
            copy.add(num);
        }
        return copy;
    }

发表于 2023-08-26 15:19:39 回复(0)
Java
帅气的小熊猫在学习头像 帅气的小熊猫在学习
dfs+回溯 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param target int整型 
     * @return int整型ArrayList<ArrayList<>>
     */
    static ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    static ArrayList<Integer> layer = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath (TreeNode root, int target) {
        // write code here
        // dfs + 回溯
        dfs(root, target);
        return result;
    }

    public static void dfs(TreeNode p, int target) {
        if (p == null) return;
        layer.add(p.val);
        if ((target -= p.val) == 0 && p.left == null && p.right == null) {
            result.add(new ArrayList<Integer>(layer));
            // 优化
            layer.remove(layer.size() - 1);
            return;
        }
        dfs(p.left, target);
        dfs(p.right, target);
        layer.remove(layer.size() - 1);
    }
}


发表于 2023-07-17 16:51:40 回复(0)
Java
MorpheusNeo头像 MorpheusNeo 
import java.util.ArrayList;
import java.util.List;
/**
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 expectNumber) {
        ArrayList<ArrayList<Integer>> allPath = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> path = new ArrayList<Integer>();
        if (root == null) {
            return allPath;
        }
        path.add(root.val);
        if (root.left == null && root.right == null) {
            allPath.add(new ArrayList<Integer>(path));
        } else {
            findAllPath(allPath, path, root.left, expectNumber);
            findAllPath(allPath, path, root.right, expectNumber);
        }
        return allPath;
    }

    public void findAllPath(ArrayList<ArrayList<Integer>> allPath,
                            ArrayList<Integer> path, TreeNode node, int expectNumber) {
        if (node == null) {
            return;
        }
        path.add(node.val);
        if (node.left == null && node.right == null) {
            if (sum(path) == expectNumber) {
                allPath.add(new ArrayList<Integer>(path));
            }
        } else {
            findAllPath(allPath, path, node.left, expectNumber);
            findAllPath(allPath, path, node.right, expectNumber);
        }
        path.remove(path.size() - 1);
    }

    public int sum(ArrayList<Integer> list) {
        return list.stream().filter(item->item != null).mapToInt(item->item).sum();
    }
}

发表于 2023-05-08 10:06:02 回复(0)
Java
愉快的猕猴桃在泡池子头像 愉快的猕猴桃在泡池子
测试用例是不是有一点问题呀，第13组用例这里提示是{10,5,12,4,7},15；预期输出是[]。实际输出是[[10,5]]。但是显然[10,5]是一条所求路径呀。 
public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        ArrayList<ArrayList<Integer>> listOfLists = new ArrayList<>();
        if(root==null)
            return listOfLists;
        LinkedList<Integer> list = new LinkedList<>();
        traversal(root,listOfLists,list,0,expectNumber);
        return listOfLists;
    }

    // 刚刚从根走到了nd，此时lst包含了路径上经过的节点的值(不包括nd)，sum为当前路径(不包括nd)的和。expected为期望的数字
    public void traversal(TreeNode nd, ArrayList<ArrayList<Integer>> lOL,
                          LinkedList<Integer> lst, int sum, int expected){
        sum+=nd.val;
        lst.add(nd.val);
        if(sum==expected)
            lOL.add(new ArrayList<>(lst));
        if(nd.left!=null)
            traversal(nd.left,lOL,lst,sum,expected);
        if(nd.right!=null)
            traversal(nd.right,lOL,lst,sum,expected);
        lst.pollLast(); // 恢复现场。
    }
}


发表于 2022-09-19 20:38:30 回复(2)
Java
牛客用户007头像 牛客用户007 
//内存爆炸
import java.util.*;
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 {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int expectNumber) {
        if (root == null) return res;
        ArrayList<Integer> ls = new ArrayList();
        dfs(root, 0, expectNumber, ls);
        return res;
    }

    void dfs(TreeNode root, int sum, int target, ArrayList<Integer> ls) {
        if (root == null) return;
        if (root.left == null && root.right == null && sum + root.val == target) {
            ls.add(root.val);
            res.add(new ArrayList<Integer>(ls));
            return;
        }
        ls.add(root.val);
        ArrayList<Integer> left = new ArrayList<>(ls);
        ArrayList<Integer> right = new ArrayList<>(ls);
        dfs(root.left, sum + root.val, target, left);
        dfs(root.right, sum + root.val, target, right);
    }
}

发表于 2022-09-03 12:16:42 回复(0)
Java
two倩头像 two倩
import java.util.*;
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   void Find(TreeNode root,int expectNumber, int result,  ArrayList<Integer> list, ArrayList<ArrayList<Integer>> ret){
        if(root==null)
            return ;
        //中序遍历
        list.add(root.val);
        result+=root.val;
        if(result==expectNumber&&root.right==null&&root.left==null) {//找到了,题目要求是叶子结点
         //   ret.add(list);//在这里 list后面回溯,ret内的数据会丢失
            ret.add(new ArrayList<>(list));
        }
        Find(root.left,expectNumber,result,list,ret);
        Find(root.right,expectNumber,result,list,ret);
        //每向上走一层，都会回溯
        result-=root.val;
        list.remove(list.size()-1);
        //ret【0】指向了888这个list,随着list内容的删除，ret【0】的数据也在减少 注意！！！
    }
    public  ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        if (root == null) return ret;
        Find(root, expectNumber, 0, list, ret);
        return ret;
    }

}
发表于 2022-08-21 00:09:04 回复(0)
Java
牛客839384289号头像 牛客839384289号 
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    LinkedList<Integer> queue = new LinkedList<>();
    
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        dfs(root,expectNumber);
        return res;
    }
    
    public void dfs(TreeNode root ,int num){
        if(root==null){
            return;
        }
        num-=root.val;
        queue.add(root.val);
        if(num==0 && root.left==null && root.right==null){
            res.add(new ArrayList(queue));
        }
        dfs(root.left,num);
        dfs(root.right,num);
        queue.removeLast();
    }

发表于 2022-06-16 22:43:07 回复(0)
Java
牛客546251489号头像 牛客546251489号 
public class Solution {
     ArrayList<Integer> list =new ArrayList<Integer>();
    ArrayList<ArrayList<Integer>> lists=new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
       
        if(root==null){
            return lists;
        }
        Find(root,expectNumber);
        return lists;
        
        
    }
    public void Find(TreeNode root,int expectNumber) {
        
        if(root==null){
            return;
        }
        list.add(root.val);
        expectNumber-=root.val;
        if(expectNumber==0&&root.left==null&&root.right==null){
            
            lists.add(new ArrayList<Integer> (list));//注意深浅拷贝

        }
        Find(root.left,expectNumber);
        Find(root.right,expectNumber);
        list.remove(list.size()-1);
    }
}

编辑于 2022-06-05 21:34:55 回复(0)
Java
txy_钟琛头像 txy_钟琛 
public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        FindPathDFS(root, ans, list, expectNumber);
        return ans;
    }
    private void FindPathDFS(TreeNode root, ArrayList<ArrayList<Integer>> ans, ArrayList<Integer> list, int expectNumber) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        expectNumber -= root.val;

        if (root.left == null && root.right == null && expectNumber == 0) {
            ans.add(new ArrayList<>(list));
        }
        FindPathDFS(root.left,ans,list,expectNumber);
        FindPathDFS(root.right,ans,list,expectNumber);
        list.remove(list.size()-1);
    }
}

发表于 2022-05-26 13:50:08 回复(0)
Java
只会暴力做题头像 只会暴力做题
很容易想到用前序遍历这棵树，维护一个list存储遍历的值，到了叶子节点后就把list加入到答案中，最后剔除答案中不符合题意的list即可，需要注意的是在list的维护过程中，每遍历一次，就要移除list的最后一个元素，避免重复计算
（栈的思想，但我觉得这里用list对于后面的计算更简便） 
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 static ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int expectNumber) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        ArrayList<Integer> temp = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        dfs(root, ans, temp);
        for (int i = 0; i < ans.size(); i++) {
            ArrayList<Integer> list = ans.get(i);
            int sum = 0;
            for (int j = 0; j < list.size(); j++) {
                sum += list.get(j);
            }
            if (sum != expectNumber) {
                ans.remove(list);
                i--;
            }
        }
        return ans;
    }

    private static void dfs(TreeNode root, ArrayList<ArrayList<Integer>> ans, ArrayList<Integer> temp) {
        temp.add(root.val);
        if (root.left == null && root.right == null) {
            ans.add((ArrayList<Integer>) temp.clone());
        }
        if (root.left != null) {
            dfs(root.left, ans, temp);
            temp.remove(temp.size() - 1);
        }
        if (root.right != null) {
            dfs(root.right, ans, temp);
            temp.remove(temp.size() - 1);
        }
    }
}

发表于 2022-05-18 22:09:31 回复(0)
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 {
    ArrayList<ArrayList<Integer>> ans;
    void dfs(TreeNode root,int curSum,int exp,ArrayList<Integer> path){
        // 叶子节点
        if(root.left==null&&root.right==null){
            if(curSum==exp){
                ans.add(new ArrayList<>(path));
            }
            return ;
        }
        

        if(root.left!=null){
            path.add(root.left.val);
            dfs(root.left,curSum+root.left.val,exp,path);
            path.remove(path.size()-1);
        }
        if(root.right!=null){
             path.add(root.right.val);
            dfs(root.right,curSum+root.right.val,exp,path);
            path.remove(path.size()-1);
        }
        return ;
    }
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        ans=new ArrayList<>();
        if(root==null) return ans;
        ArrayList<Integer> path=new ArrayList<>();
        path.add(root.val);
        dfs(root,root.val,expectNumber,path);
        return ans;
    }
}

发表于 2022-05-10 22:14:22 回复(0)
Java
划水的人头像 划水的人 
import java.util.*;
/**
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>> res=new ArrayList<>();
    public Stack<Integer> path=new Stack<>();
    public void dfs(TreeNode root,int target){
        if(root==null)
            return;
        path.push(root.val);
        target-=root.val;
        if(root.left==null&&root.right==null&&target==0){
            res.add(new ArrayList<Integer>(path));
        }
        dfs(root.left,target);
        dfs(root.right,target);
        path.pop();
        return;
    }
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
         dfs(root,target);
        return res;
    }
}
C转Java学生，上面我的写法习惯类C写法，看了挺多Java代码 都是下面的写法， 
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root ==null) return paths;//递归停止条件 但为什么返回个paths？ 更新数据不就可以了吗
        path.push(root.val);
        target -= root.val;
 
        if(target == 0 && root.left == null && root.right ==null){
            paths.add(new ArrayList<Integer>(path));
        }
 
        FindPath(root.left,target); //返回的paths到哪里了
        FindPath(root.right,target); //返回的paths到哪里了
        path.pop();
为什么要返回个没用的数据？
发表于 2022-04-13 13:12:36 回复(0)
Java
图南qqqq头像 图南qqqq 
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 expectNumber) {
        ArrayList<ArrayList<Integer>> paths = new ArrayList<>();
        ArrayList<Integer> path = new ArrayList<>();
        if (root==null) return paths;
        dfs(root, expectNumber, paths, path);
        return paths;
    }
    public void dfs(TreeNode root, int num, ArrayList<ArrayList<Integer>> paths,ArrayList<Integer> path){
        path.add(root.val);
        if (root.left==null && root.right==null && root.val ==num){
            paths.add(new ArrayList<Integer>(path));
        }
        if (root.left!=null) 
            dfs(root.left, num-root.val, paths, path);
        if (root.right!=null)
            dfs(root.right, num-root.val, paths, path);
        path.remove(path.size()-1);
    }
}

发表于 2022-03-06 13:15:48 回复(0)
Java
感性的华夫饼刷牛客头像 感性的华夫饼刷牛客 
public class Solution {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
     ArrayList<Integer> path = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        if(root == null)return ans;
        
        find(root, expectNumber);
        
        return ans;
    }
    
     void find(TreeNode root,int expectNumber){
        path.add(root.val);
        expectNumber -= root.val;
        
        if(expectNumber == 0 && root.left == null && root.right == null){
            ans.add(new ArrayList<>(path));                        
        }
         
         if(root.left != null){
             find(root.left, expectNumber);
         }
         
         if(root.right != null){
             find(root.right, expectNumber);
         }
         
         path.remove(new Integer(root.val));
          
    }
}

发表于 2022-02-27 22:09:04 回复(0)
Java
牛客989812257号头像 牛客989812257号 
public class Solution {
  public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
    ArrayList<ArrayList<Integer>> result = new ArrayList();
    ArrayList<Integer> path = new ArrayList();
    process(root,expectNumber,0,result,path);
    return result;
  }
  private void process(TreeNode root,int expectNumber,int curSum,
               ArrayList<ArrayList<Integer>> result,ArrayList<Integer> path){
    if(root == null){
      return;
    }
    curSum += root.val;
    path.add(root.val);
    if(curSum==expectNumber && root.left==null && root.right==null){
      result.add(new ArrayList<Integer>(path));
      path.remove(path.size()-1);
      return;
    }
    process(root.left,expectNumber,curSum,result,path);
    process(root.right,expectNumber,curSum,result,path);
    path.remove(path.size()-1);
  }
}

发表于 2022-01-27 21:43:27 回复(0)
Java
浮鸟(BAT实习ing，目标外企~)头像 浮鸟(BAT实习ing，目标外企~)
dfs+deque为模板的回溯&剪枝 
import java.util.*;
public class Solution {
    // 定义全局arr减少参数
    ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
    // 用栈作为模板，实时记录
    Deque<Integer> deque = new LinkedList<>();
    
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        addPath(root,expectNumber);
        return ret;
    }
    
    public void addPath(TreeNode root, int expectNumber){
        // 判空
        if(root==null){
            return;
        }
        // 每遍历到一个结点，先入队
        deque.addLast(root.val);
        // 如果左右节点为空时，sum-val恰好=0，说明找到一条路径，立即以当前deque为模板, 创建新链表加入ret
        if(root.left==null && root.right==null && expectNumber-root.val==0){
            ret.add(new ArrayList<Integer>(deque));
        }
        // 左右子树递归
        addPath(root.left, expectNumber-root.val);
        addPath(root.right, expectNumber-root.val);
        
        // 为保持栈的实时性，当前节点左右子树递归完成后，总是将该节点值弹出（回溯的剪枝函数）
        deque.removeLast();
    }
}


发表于 2022-01-02 16:52:52 回复(1)
提交观点

问题信息

树
难度：
194条回答 179914浏览

热门推荐

通过挑战的用户

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号