剑指 Offer 34. 二叉树中和为某一值的路径

Chenyi_li / 2023-08-04 / 原文

1.先写一种错误的写法，这是自己第一次写的写法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {


    public List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        LinkedList<Integer> path = new LinkedList<>();
        fun(root,target,path);
        return ans;
    }

    public void fun(TreeNode root, int target,List<Integer> path){
        if(root==null&&target==0){
            ans.add(path);
            return;
        }
        
        if(target<=0||root==null){
            return;
        }

        

        path.add(root.val);
        List<Integer> pathLeft = new LinkedList<>(path);
        List<Integer> pathRight = new LinkedList<>(path);
        fun(root.left,target-root.val,pathLeft);
        fun(root.right,target-root.val,pathRight);
    }
}

这里要注意，List pathLeft = new LinkedList<>(path);往下递归的时候要深拷贝传递，不然修改的是同一个变量。
同时，这种写法也是不对的，最后结果有重复值。

因为当最后有满足条件的值是在为空的的时候判断的，所以左右节点为空都会产生值。

正确写法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(root, target, new ArrayList<>(), ans);
        return ans;
    }

    private void dfs(TreeNode node, int target, List<Integer> path, List<List<Integer>> result) {
        if (node == null)
            return;

        List<Integer> newPath = new ArrayList<>(path);
        newPath.add(node.val);

        if (node.left == null && node.right == null && target == node.val) {
            result.add(newPath);
        }

        dfs(node.left, target - node.val, newPath, result);
        dfs(node.right, target - node.val, newPath, result);
    }
}