狗家淀面

面试官一上来就直接贴了题目，还包括一张图，说为了节约时间就直接开始做题吧。
1.给定一棵二叉树，在这棵树中有一些节点需要被删除，现在有一个可供调用的函数shouldBeErased(Node *t)可以用来判断每个节点是否应被移除（返回一个布尔值true或者false）。在删除了那些需要被移除的节点之后，原来的二叉树就会被打散成一棵棵子树，或者说是一个森林，要求返回最终的这个森林（用一个数组来表示，数组中每个元素是对应子树的树根）。
我就说可以用DFS,从树根开始搜索，对每个节点判断一下是否应被删除，如果要删除的话就移除掉它并递归调用此函数来删除左右子树里要删除的节点并合并左右子树得到的森林，如果不删除的话也还是递归地对左右子树进行删除操作，但合并的时候稍微注意一下如果左（或右）子树的树根没有被删除，那么它应该连着当前的树根，也就是说左（右）子树得到

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

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

了一次的元素肯定在数组右半部份（假设数组下标从0开始），如果idx为奇数那么目标就在左半部分，继续这样二叉查找。

感觉是运气好碰到一个比较nice的面试官，愿意跟我聊，在写代码过程中看到了一些问题愿意给我指出来（而不是暗自给我扣分之类的），当然因为题目不难，所以基本功以及整个过程的沟通比较重要，需要比较顺畅地完成这个过程，而不要一个人闷头苦想10分钟或者一声不吭地写代码造成尴尬的冷场。过了几天HR通知接下来去onsite。

定义了一个全局变量res
一个boolean 变量来判断是root，还是非root
是root的话我们就要加入array，不是root的话 就正常遍历

1. def get_forest(self, node):
   
2.         if node is None:
   
3.                 return []
   
4.         res = []
   
5.         self.helper(node, res, True)
   
6.         return res
   
7. 
   
8. def helper(self, node, res, is_root):
   
9.         if node is None:
   
10.                 return None
    
11. 
    
12.         if shouldBeErased(root):
    
13.                 if node.left:
    
14.                         self.helper(node.left, res, True)
    
15.                 if node.right:
    
16.                         self.helper(node.right, res, True)
    
17. 
    
18.         if not shouldBeErased(root):
    
19.                 if is_root:
    
20.                         res.append(node)
    
21.                 if node.left:
    
22.                         node.left = self.helper(node.left, res, False)
    
23.                 if node.right:
    
24.                         node.right = self.helper(node.right, res, False)

复制代码

1. 
   
2. import java.util.*;
   
3. 
   
4. public class removeNodes {
   
5. 
   
6.     static class Node {
   
7.         int val;
   
8.         Node left;
   
9.         Node right;
   
10.         boolean toRemove;
    
11.         public Node(int val) {
    
12.             this.val = val;
    
13.         }
    
14.     }
    
15. 
    
16.     public static void main(String[] args) {
    
17. 
    
18. 
    
19.         Node n1 = new Node(1);
    
20.         Node n2 = new Node(2);
    
21.         Node n3 = new Node(3);
    
22.         Node n4 = new Node(4);
    
23.         Node n5 = new Node(5);
    
24.         Node n6 = new Node(6);
    
25.         Node n7 = new Node(7);
    
26. 
    
27.         n1.left = n2;
    
28.         n1.right = n3;
    
29.         n2.left = n4;
    
30.         n2.right = n5;
    
31.         n3.left = n6;
    
32.         n3.right = n7;
    
33.         n1.toRemove = true;
    
34.         n2.toRemove = true;
    
35.         n6.toRemove = true;
    
36. 
    
37.         List<Node> list = removeNodes(n1);
    
38.         for (Node n : list) {
    
39.             print(n);
    
40.         }
    
41.     }
    
42. 
    
43.     private static void print(Node root) {
    
44.         System.out.println("===");
    
45.         Deque<Node> q = new LinkedList<>();
    
46.         q.offer(root);
    
47.         while (!q.isEmpty()) {
    
48.             int size = q.size();
    
49.             while (size-- > 0) {
    
50.                 Node cur = q.poll();
    
51.                 if (cur == null) {
    
52.                     System.out.print("#");
    
53.                 } else {
    
54.                     System.out.print(cur.val);
    
55.                     q.offer(cur.left);
    
56.                     q.offer(cur.right);
    
57.                 }
    
58.             }
    
59.             System.out.println();
    
60.         }
    
61.         System.out.println("===");
    
62.     }
    
63. 
    
64.     private static List<Node> removeNodes(Node root) {
    
65.         List<Node> res = new ArrayList<>();
    
66.         if (root == null) {
    
67.             return res;
    
68.         }
    
69. 
    
70.         List<Node> left = removeNodes(root.left);
    
71.         List<Node> right = removeNodes(root.right);
    
72. 
    
73.         if (!root.toRemove) {
    
74.             res.add(root);
    
75.         }
    
76. 
    
77.         if (root.left != null && root.left.toRemove) {
    
78.             root.left = null;
    
79.         }
    
80.         if (root.right != null && root.right.toRemove) {
    
81.             root.right = null;
    
82.         }
    
83. 
    
84.         res.addAll(left);
    
85.         res.addAll(right);
    
86.         return res;
    
87.     }
    
88. 
    
89.     private static void helper(List<Node> res, Node root) {
    
90.         if (root == null) {
    
91.             return;
    
92.         }
    
93. 
    
94.         if (root.toRemove) {
    
95.             helper(res, root.left);
    
96.             helper(res, root.right);
    
97.         } else {
    
98. 
    
99.         }
    
100.     }
     
101. }
     

复制代码

补充内容 (2018-11-15 11:56):
请忽略helper函数

打错了，binary search当然复杂度是O(logn)……

楼主基本功不错。第一题bfs可破否？如果子树需要删就存入全局变量 父node里设为null

pandami 发表于 2018-8-22 08:35
楼主基本功不错。第一题bfs可破否？如果子树需要删就存入全局变量 父node里设为null

个人觉得bfs或者dfs影响不大，就是代码里面有一些细节上的处理要注意一下，比如父亲为空，或者父亲不为而子树只有一个为空/都不为空等等各种情况都考虑到就差不多

qianlizimu 发表于 2018-8-22 09:23
个人觉得bfs或者dfs影响不大，就是代码里面有一些细节上的处理要注意一下，比如父亲为空，或者父亲不为而 ...

是的 bfs不用递归不知道会不会好写一点

pandami 发表于 2018-8-22 09:35
是的 bfs不用递归不知道会不会好写一点

觉得递归好写，就像你说的把要删除的节点存到全局变量里面，如果要删除递归函数返回None，否则返回节点本身

void dfs(TreeNode node, Boolean isParentDeleted, List<TreeNode> answer)
{
...
}

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