題目
給定一個(gè)二叉樹莫换，我們?cè)跇涞墓?jié)點(diǎn)上安裝攝像頭霞玄。
節(jié)點(diǎn)上的每個(gè)攝影頭都可以監(jiān)視其父對(duì)象骤铃、自身及其直接子對(duì)象。
計(jì)算監(jiān)控樹的所有節(jié)點(diǎn)所需的最小攝像頭數(shù)量坷剧。
示例 1：
輸入：[0,0,null,0,0]
輸出：1
解釋：如圖所示惰爬，一臺(tái)攝像頭足以監(jiān)控所有節(jié)點(diǎn)。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/convert-bst-to-greater-tree
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有惫企。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)撕瞧，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
題解及思路
源碼
/**
?*?Definition?for?a?binary?tree?node.
?*?public?class?TreeNode?{
?*?????int?val;
?*?????TreeNode?left;
?*?????TreeNode?right;
?*?????TreeNode(int?x)?{?val?=?x;?}
?*?}
?*/
class?Solution?{
????private?int?total?=?0;
????public?int?minCameraCover(TreeNode?root)?{
????????if(root==null)
????????????return?total;
????????if(dfs(root)==2)
????????????total++;
????????return?total;
????}
????public?int?dfs(TreeNode?node){
????????if(node==null)
????????????return?1;
????????int?left?=?dfs(node.left);
????????int?right?=?dfs(node.right);
????????if(left==2||right==2){
????????????total++;
????????????return?0;
????????}else?if(left==0||right==0){
????????????return?1;
????????}else{
????????????return?2;
????????}
????}
}
