968. 監控二叉樹
題解
? 關于樹的問題我們一般使用遞回來解決，首先可以遍歷到樹的最底端(此節點的左右孩子都為空，空孩子標記為狀態1)，標記此節點為已覆寫(狀態0)，如果一個節點的其中一個左右節點狀態為已覆寫(即還未安裝監視器)，那么給此節點安裝監視器，并且記錄監視器數量的全域變數自增，
? 安裝監視器后，給節點標記狀態為2，那么它的父節點就會被此監視器監控，即父節點已被覆寫，狀態為1，
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int minCameraCover(TreeNode root) {
if (lrd(root) == 0) {
res++;
}
return res;
}
int res=0;
int lrd(TreeNode node) {
if (node == null) {
return 1;
}
int left=lrd(node.left);
int right=lrd(node.right);
if (left == 0 || right == 0) {
res++;
return 2;
}
if(left==1&&right==1){
return 0;
}
if(left+right>=3){
return 1;
}
return -1;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/112149.html
標籤：其他