979. Distribute Coins in Binary Tree

Link

Solution

這題困難點是如何想到用DFS去簡化問題

DFS思路

• 推演的過程中要告訴我們什麼?

  • 狀態的更新 (global variable)

    • 移動步數

  • 子問題的答案 (return value)

    • 差or多 多少coins

設計DFS(node) 的return是該node包含其子node所能夠提供的多餘coins數(正數)or所缺少的node數(負數)。

之後就是一層層去DFS每層就是會增加move數為 (左子樹的多餘(缺少) coins) + ( 右子樹的多餘(缺少) coins)

   int ret = 0;
    public int distributeCoins(TreeNode root) {
        dfs(root);
        return ret;
    }
    
    //the excess coins of the node
    // negative : to send in {number_of_conins} into the node to lets subnode's coin can be one
    // positive : to send out {number_of_conins} into the node to lets subnode's coin can be one
    public int dfs(TreeNode node){
        if(node == null) return 0;
        //推演
        int leftExcess = dfs(node.left);
        int rightExcess = dfs(node.right);
        //結算
        ret += Math.abs(leftExcess) + Math.abs(rightExcess);
        return node.val + leftExcess + rightExcess - 1;
    }