题目描述

解题思路

典型的路径问题，分多条路径和一条路径，也就是返回值不同。
具体链接🔗

    class Solution {
        // 方法一
        /*public List<List<Integer>> pathSum(TreeNode root, int target) {
            if (root == null) {
                return res;
            }
            int count = target - root.val;
            dfs(root, path, count);
            return res;
        }
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        public void dfs(TreeNode root, LinkedList<Integer> path, int count) {
            path.add(root.val);
            if (root.left == null && root.right == null) {
                if (count == 0) {
                    res.add(new LinkedList<>(path));
                }
                return;
            }
            if (root.left != null) {
                count -= root.left.val;
                dfs(root.left, path, count);
                count += root.left.val;    // 回溯
                path.removeLast();
            }
            if (root.right != null) {
                count -= root.right.val;
                dfs(root.right, path, count);
                count += root.right.val;    // 回溯
                path.removeLast();
            }
            return;
        }*/
        // 方法二
        LinkedList<List<Integer>> res = new LinkedList<>();
        LinkedList<Integer> path = new LinkedList<>();
        public List<List<Integer>> pathSum(TreeNode root, int target) {
            recur(root, target);
            return res;
        }
        public void recur(TreeNode root, int tar) {
            if (root == null) {
                return;
            }
            path.add(root.val);
            tar -= root.val;
            // 注意判断左右孩子
            if (tar == 0 && root.left == null && root.right == null) {
                res.add(new LinkedList(path));
            }
            recur(root.left, tar);
            recur(root.right, tar);
            path.removeLast();
        }
    }