题解 | #牛奶产量总和#

知识点：递归

思路: 还是那句话理解递归的本质，可以发现这个路径其实就是递归的路程，

那么，我们只需要维持一个可变长的数组，递归则加深，递归回去就减少，

递归到叶子节点的时候，我们就计算和

改进：这里我是传入的参数数组cur进去的，添加和remove元素，但是其实在函数里声明

一个数组，然后直接添加元素也是可以的，因为，当递归回调的时候，就会返回最初添加的状态

编程语言：java

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类
     * @return int整型
     */
    public int compute(List<Integer> list) {
        //根据数组计算数字
        int sum = 0;
        int k = 1;
        for (int i = list.size() - 1; i >= 0; i--) {
            sum += list.get(i) * k;
            k = k * 10;
        }
        return sum;
    }
    public void get_rootToLeaf_sum(TreeNode root, List<Integer> cur,
                                   List<Integer> result) {
        if (root == null)
            return;
        //前置处理
        if (root != null)
            cur.add(root.val);
        if (root.left == null && root.right == null) {
            //叶子节点的时候，一次奶牛路径
            //处理cur
            result.add(compute(cur));
        }
        get_rootToLeaf_sum(root.left, cur, result);
        get_rootToLeaf_sum(root.right, cur, result);
        //后置处理
        //处理节点4完事后的事情，回到2
        //这里长度减1其实就可以了
        cur.remove(cur.size() - 1);
    }
    public int sumNumbers (TreeNode root) {
        // write code here
        List<Integer> cur = new ArrayList<>();
        List<Integer> result = new ArrayList<>();
        get_rootToLeaf_sum(root, cur, result);
        int sum = 0;
        for (int i = 0; i < result.size(); i++)
            sum += result.get(i);
        return sum;
    }
}