剑指offer-二叉树中和为某一值的路径

题目描述

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

/**
     * 1.前序遍历，从根结点开始，添加到暂存路径中，直到叶子结点。如果当前路径和为target，则是一条有效路径
     * 如果和不等于target，将叶子结点从暂存路径中去除，寻找其他路径
     * @param root
     * @param target
     * @return
     */
    public ArrayList<ArrayList<Integer>> findPath(TreeNode root, int target) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); // 保存有效路径
        if(root == null)
            return res;
        
        ArrayList<Integer> path = new ArrayList<Integer>();// 暂存路径
        
        int sum = 0;
        findPath(sum, res, path, root, target);
        
        return res;
    }

    private void findPath(int sum, ArrayList<ArrayList<Integer>> res,
            ArrayList<Integer> path, TreeNode root, int target) {
        
        if(root == null) return;
        path.add(root.value);
        sum += root.value;
        // 如果是叶子结点，并且sum == target ,即为有效路径
        if(sum == target && root.left == null && root.right == null) {
            // 创建新的ArrayList保存有效路径中的值，再放到有效路径集合中
            ArrayList<Integer> pathList = new ArrayList<Integer>();
            for (int i = 0; i < path.size(); i++) {
                pathList.add(path.get(i));
            }
            res.add(pathList);
        }
        
        // 如果不是叶子结点
        if(root.left != null) {
            findPath(sum, res, path, root.left, target);
        }
        if(root.right != null) {
            findPath(sum, res, path, root.right, target);
        }
        
        sum -= root.value;   // 在sum减去当前的值
        path.remove(path.size()-1);   // 在返回父节点之前，删除路径上的当前结点
        
    }