刷題-Leetcode-968. 監控二叉樹(二叉樹)

968. 監控二叉樹

題目連結

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/binary-tree-cameras/submissions/

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

題目描述

給定一個二叉樹，我們在樹的節點上安裝攝像頭。

節點上的每個攝影頭都可以監視其父對象、自身及其直接子對象。

計算監控樹的所有節點所需的最小攝像頭數量。

示例 1：

輸入：[0,0,null,0,0]

輸出：1

解釋：如圖所示，一台攝像頭足以監控所有節點。

示例 2：

輸入：[0,0,null,0,null,0,null,null,0]

輸出：2

解釋：需要至少兩個攝像頭來監視樹的所有節點。 上圖顯示了攝像頭放置的有效位置之一。

題目分析

使用c++記得手動管理記憶體。從記憶體中删除移除的節點。要養成這個好習慣。

設定虛拟節點也是一個常用的方法。

要學會自己定義節點。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* cur = dummy;

        while(cur->next){
            if(cur->next->val == val){
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }else{
                cur = cur->next;
            }
        }
        return dummy->next;
    }
};