题解 | #二叉树中和为某一值的路径(二)#

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 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param target int整型 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> FindPath (TreeNode root, int target) {
        // write code here
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if(root == null){
            return result;
        }

        if(root.val == target && root.left == null && root.right == null){
            ArrayList<Integer> list = new ArrayList<Integer>();
            list.add(target);
            result.add(list);
            return result;
        }

        ArrayList<ArrayList<Integer>> leftResult = FindPath(root.left, target - root.val);
        ArrayList<ArrayList<Integer>> rightResult = FindPath(root.right, target - root.val);

        result.addAll(leftResult);
        result.addAll(rightResult);

        for(int i = 0; i < result.size(); i++){
            result.get(i).add(0, root.val);
        }

        return result;
    }
}

主要思路还是递归，把二叉树的问题拆解成左右子树的问题，同时确定结束条件。