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

Java

牛客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

终于过了

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

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

//内存爆炸
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倩

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号

    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号

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_钟琛

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

月薪600的讨饭人

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

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号

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，目标外企~)

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)

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

输入

输出

说明

输入

输出

输入

输出

输入

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题