Leetcode979 : Distribute Coins in Binary Tree 二叉树均匀分配硬币问题

问题

给定一个二叉树的root节点，二叉树中每个节点有node.val个coins，一种有N coins。现在要求移动节点中的coins 使得二叉树最终每个节点的coins value都为1。每次移动，我们只能向相邻接点移动，也就是说coins 只能向父节点或者子节点移动，那么求最终需要移动多少步。

Leetcode原题链接: https://leetcode.com/problems/distribute-coins-in-binary-tree/

分析

如果叶子节点有0个coins，那么我们需要从parent节点移一个coin到叶子节点 (push (-1) 个coin from left node); ----move一次

如果说叶子节点有四个节点那么我们则需要push三个coins到父节点(push +3 coins from leaf node)。----move 三次

定义一个dfs(node)函数，用于表示需要从当前节点push 到its parent节点的coins个数(换句话说就是以当前节点为root的子树中的硬币总数减去当前总数节点的个数)，那么dfs(node) = dfs(node.left) + dfs(node.right) - 1 (减去一个1是因为留一个coin在当前节点) ，而使得以当前节点为root节点需要移动的步数等于abs(dfs(node.left)) + abs(dfs(node.right))。

实现

  private int ans = 0;

  public int distributeCoins(TreeNode root) {

        ans = 0;

        distributeCoinsHelper(root);

        return ans;

    }

    private int dfs(TreeNode cur){

        if(cur == null){

            return 0;

        }

        int left = dfs(cur.left);

        int right = dfs(cur.right);

        ans += Math.abs(left) + Math.abs(right);

        return left + right + cur.val - 1;

    }

巴特西

Leetcode979 : Distribute Coins in Binary Tree 二叉树均匀分配硬币问题

问题

分析

实现

最新文章

热门文章