FB跪经，疑似新题，我是没见过

中国人面的，打了个招呼就开始做题，一共四十五分钟

就一道题：

remove as many edges as possible from a tree and the result trees all have even number of nodes

         o

  /    |   |   \

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

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

/div>

第一次记录所有以当前node为根的subtree的node总数

第二次就可以用这些数据切割树了

当时脑子糊住没想到

修改了一下，可以跑楼主给的例子了。

1. 
   
2. public class TreeNode{
   
3.     int val;
   
4.     List<TreeNode> subtree;
   
5.     public TreeNode(int val){
   
6.         this.val = val;
   
7.         subtree = new ArrayList<>();
   
8.     }
   
9. 
   
10.     public void addChild(TreeNode child){
    
11.         subtree.add(child);
    
12.     }
    
13. }
    
14. 
    
15. public class BreakTree {
    
16. 
    
17.     public List<TreeNode> breakTree(TreeNode root){
    
18.         List<TreeNode> result = new ArrayList<>();
    
19.         countAndBreak(result, root);
    
20.         return result;
    
21.     }
    
22. 
    
23.     private int countAndBreak(List<TreeNode> result, TreeNode root){
    
24.         if (root == null){
    
25.             return 0;
    
26.         }
    
27. 
    
28.         int count = 1;
    
29.         Iterator<TreeNode> iter = root.subtree.iterator();
    
30.         while (iter.hasNext()){
    
31.             int childCount = countAndBreak(result, iter.next());
    
32.             if (childCount == 0){
    
33.                 iter.remove();
    
34.             } else{
    
35.                 count += childCount;
    
36.             }
    
37.         }
    
38. 
    
39.         if (count % 2 == 0){
    
40.             result.add(root);
    
41.             return 0;
    
42.         } else{
    
43.             return count;
    
44.         }
    
45.     }
    
46. 
    
47. 
    
48.     public static void main(String[] args){
    
49.         TreeNode root = new TreeNode(0);
    
50. 
    
51.         TreeNode firstChild = new TreeNode(1);
    
52.         firstChild.addChild(new TreeNode(2));
    
53.         root.addChild(firstChild);
    
54. 
    
55.         root.addChild(new TreeNode(3));
    
56.         root.addChild(new TreeNode(4));
    
57.         root.addChild(new TreeNode(5));
    
58. 
    
59.         BreakTree soln = new BreakTree();
    
60.         List<TreeNode> result = soln.breakTree(root);
    
61.         System.out.println(result.size());
    
62.     }
    
63. }
    

复制代码

jialiu54321 发表于 2016-10-18 06:23
一个空白的编辑器，所有都要自己写，包括TreeNode，test case等等

楼主运气真好差。。。这国人大哥坑爹呀。。。

楼主运气好差。。摸摸。。。

这题的输入类型是什么？多叉树node吗？

iPhD 发表于 2016-10-18 06:21
楼主运气好差。。摸摸。。。

这题的输入类型是什么？多叉树node吗？

一个空白的编辑器，所有都要自己写，包括TreeNode，test case等等

这貌似是hackerrank的原题，https://www.hackerrank.com/challenges/even-tree

您好！
本帖隐藏的内容需要积分高于 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

rinto 发表于 2016-10-18 08:41
确实没见过这种题，很tricky啊，开始还以为要先把树转化成图来做，仔细看了一下输出要求仍然是树，估计面试 ...

1. public class EvenTree {
   
2. 
   
3.     private Set<Integer>[] adj;
   
4.     private boolean[] visited;
   
5.     private int E;
   
6.     private int V;
   
7.     private int count;
   
8.     private List<Integer> nodes;
   
9. 
   
10.     public EvenTree(int E, int V) {
    
11.         adj = new (HashSet<Integer>) Object[V];
    
12.         visited = new boolean[V];
    
13.         this.E = E;
    
14.         this.V = V;
    
15.         count = 0;
    
16.         nodes = new ArrayList<Integer>();      
    
17.     }
    
18. 
    
19.     public int dfs(int node) {
    
20.         visit[node] = true;
    
21.         int children = 0;
    
22. 
    
23.         for (Integer v : adj[node]) {
    
24.             if (!visit[v]) {
    
25.                 int num = dfs(v);
    
26.                 if (num % 2 == 0) {
    
27.                     count++;
    
28.                 } else {
    
29.                     children += num;
    
30.                 }
    
31.             }
    
32.         }
    
33. 
    
34.         if (children % 2 == 1) {
    
35.             nodes.add(node);
    
36.         }
    
37.         
    
38.         return children + 1;
    
39.     }
    
40. 
    
41.     public static void main(String[] args) {
    
42.         EvenTree et = new EvenTree(E, V);
    
43.         for (int i = 0; i < E; i++) {
    
44.             et.adj[v1].add(v2);
    
45.             et.adj[v2].add(v1);
    
46.         }
    
47. 
    
48.         et.dfs(0);
    
49.     }
    
50. 
    
51. }

复制代码

遍历一遍 只要children有even个 就cut加入forest