leetcode 968 979 解题思路记录

Posted on | In ,

Medium Leetcode 979 Distribute Coins in Binary Tree

做tree的高频题碰到979卡住了，一道 uber, microsoft面试中都出现过的题。题干参考Leetcode，大概就是要把硬币分给每一个node，求最短分发路径。参考了lee215的答案，记录一下思路。

这题的解法思路是bottom to top的，所以用dfs + recursive来解。

  • 对于leaf node

    • 当value = 1时，它自给自足不向parent node要coin也不给coin
    • 当value > 1时，它给parent零花钱 = 他拥有的coin - 1
    • 当value = 0时，它向parent要1钱

    那么leaf就向上返回一个信号，range为[-1, +∞]，这个range的绝对值，就是该leaf会消耗的步数。

  • 对于非leaf node

    非leaf node会收到子女们的信号，可能有的子女给钱（正值）有的要钱（负值），也可能通通给钱或要钱。如果有子女缺钱，那么父母可能拿自己的积蓄或者其他子女孝敬他的钱来补贴（细细体会，有贪心算法内味儿了），最后，该node返回的balance为left + right + node.val - 1 （别忘了给自己留一块钱），有缺钱或者有余钱，再发送一个信号给祖父母。

最后的最后，共产主义实现了。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def distributeCoins(self, root: TreeNode) -> int:
        self.res = 0
        def dfs(root):
            if not root:
                return 0
            left = dfs(root.left)
            right = dfs(root.right)
            self.res += abs(left) + abs(right)
            return left + right + root.val - 1
        dfs(root)
        return self.res

Hard Leetcode 968 Binary Tree Cameras

这题和前面一题基本思路是类似的，bottom to up的dfs实现。lee215的解法阐述的非常清楚，包括贪心算法的思路基础。与前一题不同的是，它不再只单纯传递一个值，而是三种状态

  • leaf
  • camera
  • camera的parent

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minCameraCover(self, root: TreeNode) -> int:
        self.res = 0
        def dfs(root):
            if not root:
                return 2
            left = dfs(root.left)
            right = dfs(root.right)
            if not left or not right:
                self.res += 1
                return 1
            if left == 1 or right == 1:
                return 2
            return 0
        return self.res + 1 if dfs(root) == 0 else self.res

这一类的题目还可以再做一下834