脸家两轮店面

一轮10/22
国人小哥，直接做题
题目是给一个binary tree，在tree上装camera，每一个camera能够监视到parent，自己和两个子节点。问最少安装多少个ca

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

话柄。。我说一个什么东西他就要问我为什么这么说或者为什么这么做。。。

求大米！

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

尝试写了下代码，好像不太对……这种情况应该返回 2？但是这么dp的话是返回 1？

1. class Solution {
   
2.     public int monitor(TreeNode root) {
   
3.         int[] dp = helper(root);
   
4.         return Math.min(dp[0], dp[1]);
   
5.     }
   
6.    
   
7.     private int[] helper(TreeNode root) {
   
8.         if (root == null) {
   
9.             return new int[2];
   
10.         }
    
11.         
    
12.         if (root.left == null && root.right == null) {
    
13.             return new int[] {0, 1};
    
14.         }
    
15.         
    
16.         int[] dp = new int[2];
    
17.         int[] left = helper(root.left);
    
18.         int[] right = helper(root.right);
    
19.         
    
20.         dp[0] = Math.min(left[0] + right[1], Math.min(left[1] + right[0], left[1] + right[1]));
    
21.         dp[1] = Math.min(left[0] + right[0], Math.min(left[0] + right[1], left[1] + right[0])) + 1;
    
22.         
    
23.         return dp;
    
24.     }
    
25. }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

哇，LZ 收到 offer 了么？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

感觉装摄像头像dp吧

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ky012 发表于 2018-11-3 09:53
表示以该节点为根节点，dp[0] 表示该节点不装camera使得整个subtree都被监视到需要的最小camera数, dp[1] ...

是这个思路

感觉一个node的左右child都是leaf的case还得再分开讨论