leetcode 968. 监控二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minCameraCover(TreeNode* root, int& result)
    {
        if (root == NULL)
        {
            return 1; // 空节点都设置为被覆盖，可以使叶子节点设置为2，根据父节点情况决定是否被覆盖
        }
        int left = minCameraCover(root->left, result);
        int right = minCameraCover(root->right, result);
        // cout << "left: " << left << " right: " << right << endl;
        if (left == 1 && right == 1)
        {
            return 2;
        }
        if (left == 2 || right == 2)
        {
            result++;
            return 0;
        }
        if (left == 0 || right == 0)
        {
            return 1;
        }
        return -1;
    }
    int minCameraCover(TreeNode* root) {
        // 节点有3种状态，装监控，被覆盖，没被覆盖 分别设置为0, 1, 2，没被扫描的设置为-1
        // 从下往上扫描，叶子节点不加监控，扫描到叶子节点直接设置为2
        // 当前节点存在3中情况 1. 叶子节点有监控，当前节点被覆盖 2. 叶子节点有一个没被覆盖，当前节点装监控 3. 当前节点叶子节点都被覆盖，当前节点置为没被覆盖，先不决定装不装监控
        int result = 0;
        if (root == NULL)
        {
            return result;
        }
        int ret = minCameraCover(root, result);
        // cout << "ret: " << ret << endl;
        if (ret == 2)
        {
            result = result + 1;
        }
        return result;

    }
};