Facebook 新鲜面经

第一题

1. public class Solution {
   
2.   public LinkedList<Integer> s(TreeNode root) {
   
3.     LinkedList<Integer> ret = new LinkedList<>();
   
4.     if (root == null) {
   
5.       return ret;
   
6.     }
   
7.     Deque<TreeNode> queue = new ArrayDeque<>();
   
8.     queue.offer(root);
   
9.     ret.add(root.val);
   
10.     while (!queue.isEmpty()) {
    
11.       TreeNode tn = queue.poll();
    
12.       if (tn.left != null) {
    
13.         queue.offer(tn.left);
    
14.         ret.add(tn.left.val);
    
15.       } else {
    
16.         ret.add(null);
    
17.       }
    
18.       if (tn.right != null) {
    
19.         queue.offer(tn.right);
    
20.         ret.add(tn.right.val);
    
21.       } else {
    
22.         ret.add(null);
    
23.       }
    
24.     }
    
25.     return ret;
    
26.   }
    
27. 
    
28.   public TreeNode d(LinkedList<Integer> list) {
    
29.     if (list.isEmpty()) {
    
30.       return null;
    
31.     }
    
32.     Iterator<Integer> it = list.iterator();
    
33.     TreeNode ret = new TreeNode(it.next());
    
34.     Deque<TreeNode> queue = new ArrayDeque<>();
    
35.     queue.offer(ret);
    
36.     while (!queue.isEmpty()) {
    
37.       TreeNode tn = queue.poll();
    
38.       Integer left = it.next();
    
39.       Integer right = it.next();
    
40.       if (left != null) {
    
41.         tn.left = new TreeNode(left);
    
42.         queue.offer(tn.left);
    
43.       }
    
44.       if (right != null) {
    
45.         tn.right = new TreeNode(right);
    
46.         queue.offer(tn.right);
    
47.       }
    
48.     }
    
49.     return ret;
    
50.   }
    
51. 
    
52.   public static void main(String[] args) {
    
53.     TreeNode tn1 = new TreeNode(1);
    
54.     TreeNode tn2 = new TreeNode(2);
    
55.     TreeNode tn3 = new TreeNode(3);
    
56.     TreeNode tn4 = new TreeNode(4);
    
57.     TreeNode tn5 = new TreeNode(5);
    
58.     TreeNode tn6 = new TreeNode(6);
    
59.     TreeNode tn7 = new TreeNode(7);
    
60.     TreeNode tn8 = new TreeNode(8);
    
61. 
    
62.     tn1.left = tn2;
    
63.     tn1.right = tn3;
    
64.     tn2.left = tn4;
    
65.     tn3.left = tn5;
    
66.     tn5.left = tn6;
    
67.     tn5.right = tn7;
    
68.     tn6.left = tn8;
    
69. 
    
70.     Solution ss = new Solution();
    
71.     TreeNode r = ss.d(ss.s(tn1));
    
72.     System.out.println(ss.sameTree(tn1, r));
    
73.     TreeNode r2 = ss.d(ss.s(null));
    
74.     System.out.println(ss.sameTree(null, r2));
    
75.     return;
    
76.   }
    
77. 
    
78.   private boolean sameTree(TreeNode r1, TreeNode r2) {
    
79.     if (r1 == null && r2 == null)
    
80.       return true;
    
81.     if (r1 != null && r2 != null && r1.val == r2.val)
    
82.       return sameTree(r1.left, r2.left) && sameTree(r1.right, r2.right);
    
83.     return false;
    
84.   }
    
85. }
    

复制代码

sealove999 发表于 2016-4-3 03:57

应该不需要再少一遍找最大值或最小值，最大值和最小值肯定在两边

iwofr 发表于 2016-2-19 14:00
min不一定是drop那头的比如0 1 2 3 4 3 2， max是4，min是0， 但是max drop是4-2=2
个人觉得应该是先用 ...

二分法如何找到极大值？ 因为有重复 感觉无法排除另一半啊，比如 3，1，2，4，5 。mid = 2的时候依然无法知道极小值在mid的哪一边