题解 | Java-回溯法-二叉树根节点到叶子节点和为指定值的路径

回溯法

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型ArrayList<ArrayList<>>
     */
    
    ArrayList<ArrayList<Integer>> res=new ArrayList<>();
    ArrayList<Integer> tmp = new ArrayList<>();
    int target = 0;
    int nowsum = 0;
    public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
        // write code here
        if (root==null) return res;
        target = sum;
        dfs(root);
        return res;
    }

    public void dfs (TreeNode root) {
        tmp.add(root.val);
        nowsum += root.val;
        //判断是否为叶子节点，当前nowsum是否与sum相等，
        if (root.right == null && root.left == null && target == nowsum) {
            //相等就将list加入到结果中，
            res.add(new ArrayList<>(tmp));
            tmp.remove(tmp.size()-1);
            nowsum -= root.val;
            return; // 一个add一个remove，由于提前return走不到下面remove，所以需要remove
        }
        if (root.left!=null) {
            dfs(root.left);
        }
        if (root.right!=null){
            dfs(root.right);
        }
        tmp.remove(tmp.size()-1);
        nowsum -= root.val;
    }
}