Leetcode 968. Binary Tree Cameras

[Woodyiiiiiii]

这是一个种树状DP的类型题目。

普通算法模型是：

1. 后序遍历树
2. 每次遍历，结合左右子树返回的结果和自身的值，构成下一个结果往上传递(结果可以是状态值/差值等)
3. 最终用静态变量存储答案

class Solution {

    // 0 represent no camera cover, 1 represent camera, 2 represent camera cover
    int ans = 0;

    public int minCameraCover(TreeNode root) {
        return postorder(root) == 0 ? ans + 1 : ans;
    }

    private int postorder(TreeNode root) {
        if (root == null) {
            return 2;
        }
        int left = postorder(root.left);
        int right = postorder(root.right);
        if (left == 0 || right == 0) {
            ++ans;
            return 1;
        } else if (left == 1 || right == 1) {
            return 2;
        } else {
            return 0;
        }
    }

}

---

类似题目：

• 979. Distribute Coins in Binary Tree
• 834. Sum of Distances in Tree
• 2246. Longest Path With Different Adjacent Characters
• 原地址