• 題目鏈接:

https://leetcode-cn.com/problems/distribute-coins-in-binary-tree/

要求計算得出總共需要多少次移動才能使得每個節(jié)點上都有一個硬幣。

• 解題思路:

這道題一開始陷入dfs, 根左右, 陷入遞歸和回朔中，思路就已經(jīng)錯了。無法自拔?？戳讼骂}解，其實二叉樹的問題就是分解。不斷分解子問題。分解過程就是遞歸過程。然后只需要處理最后根節(jié)點即可。

因為是個二叉樹, 所以可以當成一個根節(jié)點，一個左節(jié)點，一個右節(jié)點，處理，只要左右兩邊都處理完了，再去處理根節(jié)點(root.val = root.left.val + root.right.val)。這個遍歷方式就是后續(xù)遍歷。

左右節(jié)點與根節(jié)點的關系, 如果左右節(jié)點金幣數(shù)為x，y。則 移動次數(shù)為 |x-1| + |y-1|

代碼如下:

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 * int val;

 * TreeNode left;

 * TreeNode right;

 * TreeNode(int x) { val = x; }

 * }

 */

class Solution {

    private int cnt;

    public int distributeCoins(TreeNode root) {

        cnt = 0;

        dfs(root);

        return cnt;

    }

    private int dfs(TreeNode node) {

        if (node == null) {

            return 0;

        }

        if (node.left != null) {

            node.val += dfs(node.left);

        }

        if (node.right != null) {

            node.val += dfs(node.right);

        }

        cnt += Math.abs(node.val - 1);

        return node.val - 1;

    }

}