脸家两轮店面

楼主一面的那道题是怎么做的？

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

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

dp[0] 只要左右儿子有一个安了就可以，cover住父亲节点。至于有一个期中有一个儿子没安装的情况可以由其孙子安装来cover未安装的那个儿子。那个single without children 的确是个corner case

尝试写了下代码，好像不太对……这种情况应该返回 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

真是没想到要用dp，面试时?紧张更想不出来了，楼主真厉害！

ky012 发表于 2018-11-3 07:33
想按回车，结果发出去了
dp[0] = min(left[0] + right[1], right[0] + left[1], right[1] + left[1])
d ...

如果只有一个node，你的方法返回0，但应该是1吧

update一下 11.6上午拿到了offer