国内某大厂笔试

给一颗二叉树（不一定是complete或balanced），要求从任意一个叶子节点往上remove，直到remove完根节点，求剩下的树的个数的最大值，输入：第一行表示有多少个节点n, 第1~n-1行表示(u,v)在树中u指向v。例子：
7
1 2
1 3
2 4
2 5
3 6
3 7

删除4的叶节点之后剩下：

这样一共还有两个树，所以返回2（同时这也是最多的树的数量）

我当时只想出了硬做的办法：建图用union find最后找remove（remove就是把根设置成-1）过后的根不为-1的数量，之后再recover这棵树，但是显然这么做复杂度很差，相信有更好的做法。

求大佬给点思路

找到某个有sibling总数最多的path

补充内容 (2020-9-4 23:27):
剩下的树的个数就是sibling的个数

1. public int getMaxIslandsAfterDeletion(TreeNode root) {
   
2.     return dfs(root, 0);
   
3.   }
   
4. 
   
5.   // otherIslandsLeft means if node were deleted, how many other islands above node will survive
   
6.   public int dfs(TreeNode node, int otherIslandsLeft) {
   
7.     int best = otherIslandsLeft;
   
8.     // because both node exist, therefore no matter which child is deleted (by definition, I will
   
9.     // also be removed), the other child node will survive
   
10.     if (node.left != null && node.right != null) {
    
11.       best = Math.max(best, otherIslandsLeft + 2);
    
12.       best = Math.max(best, dfs(node.left, otherIslandsLeft + 1));
    
13.       best = Math.max(best, dfs(node.right, otherIslandsLeft + 1));
    
14.     } else if (node.left != null && node.right == null) {
    
15.       best = Math.max(best, otherIslandsLeft + 1);
    
16.       best = Math.max(best, dfs(node.left, otherIslandsLeft));
    
17.     } else if (node.left == null && node.right != null) {
    
18.       best = Math.max(best, otherIslandsLeft + 1);
    
19.       best = Math.max(best, dfs(node.right, otherIslandsLeft));
    
20.     } // otherwise, null, null, do nothing
    
21.     return best;
    
22.   }

复制代码

和楼上做法其实一样

1. struct Node {
   
2.     Node *l = nullptr;
   
3.     Node *r = nullptr;
   
4. };
   
5. 
   
6. // return number of islands if a path is removed from tree "p"
   
7. int dp(Node* p) {
   
8.     if (p->l == nullptr && p->r == nullptr) return 0;
   
9.     if (p->l == nullptr) return dp(p->r);
   
10.     if (p->r == nullptr) return dp(p->l);
    
11.     return 1+max(dp(p->l), dp(p->r));
    
12. }

复制代码