二叉树分派硬币 Distribute Coins in Binary Tree

2019-03-27 15:53:38

问题描述：

问题求解：

很有意思的题目。充分体现了二叉树的自底向上的递归思路。

自底向上进行运算，对于最底层的二叉子树，我们需要计算每个节点向其parent传送多余的硬币数量，不论正负，都是需要占用move数量的。自此递归的进行计数即可。

    public int distributeCoins(TreeNode root) {

        int[] res = new int[1];

        helper(root, res);

        return res[0];

    }

    private int helper(TreeNode root, int[] res) {

        if (root == null) return 0;

        int l = helper(root.left, res);

        int r = helper(root.right, res);

        res[0] += Math.abs(l) + Math.abs(r);

        return l + r + root.val - 1;

    }