Fackbook 下午刚电面的面筋

douya 发表于 2015-3-12 11:32
第三题能详细说下吗？

第三题就是BST转成一个循环的linkedlist，用left right 当prev next 的指针了，上网搜一下，都有的

fib 的log n的事先没看过现场能想出来那也太牛x了吧

第三题no extra space是要求必须用morris traversal?

1. //这是二叉树转双向链表的程序，测试通过。

复制代码

oops，没贴上

1. public class SolutionConvert {
   
2.     public void solve(TreeNode root) {
   
3.         if (root == null) {
   
4.             return;
   
5.         }
   
6.         convertToDoubleLinkedList(root);           
   
7.     }
   
8.    
   
9.     public void convertToDoubleLinkedList(TreeNode root) {
   
10.         if (root == null) {
    
11.             return;
    
12.         }
    
13.         if (root.left != null) {
    
14.             TreeNode left = root.left;
    
15.             convertToDoubleLinkedList(left);
    
16.             while (left.right != null) {
    
17.                 left = left.right;
    
18.             }
    
19.             left.right = root;
    
20.             root.left = left;
    
21.         }
    
22.         if (root.right != null) {
    
23.             TreeNode right = root.right;
    
24.             convertToDoubleLinkedList(right);
    
25.             while (right.left != null) {
    
26.                 right = right.left;
    
27.             }
    
28.             right.left = root;
    
29.             root.right = right;
    
30.         }
    
31.     }
    
32.    
    
33.     public void test(String[] args) {
    
34.         TreeNode a = new TreeNode("10");
    
35.         TreeNode b = new TreeNode("12");
    
36.         TreeNode c = new TreeNode("15");
    
37.         TreeNode d = new TreeNode("25");
    
38.         TreeNode e = new TreeNode("30");
    
39.         TreeNode f = new TreeNode("36");
    
40.         a.left = b;
    
41.         a.right = c;
    
42.         b.left = d;
    
43.         b.right = e;
    
44.         c.left = f;
    
45.         solve(a);
    
46.         while (a.left != null) {
    
47.             a = a.left;
    
48.         }
    
49.         while (a != null) {
    
50.             System.out.print(a.val + " ");
    
51.             a = a.right;
    
52.         }      
    
53.     }
    
54. }

复制代码

oops，没贴上

1. public class SolutionConvert {
   
2.     public void solve(TreeNode root) {
   
3.         if (root == null) {
   
4.             return;
   
5.         }
   
6.         convertToDoubleLinkedList(root);           
   
7.     }
   
8.    
   
9.     public void convertToDoubleLinkedList(TreeNode root) {
   
10.         if (root == null) {
    
11.             return;
    
12.         }
    
13.         if (root.left != null) {
    
14.             TreeNode left = root.left;
    
15.             convertToDoubleLinkedList(left);
    
16.             while (left.right != null) {
    
17.                 left = left.right;
    
18.             }
    
19.             left.right = root;
    
20.             root.left = left;
    
21.         }
    
22.         if (root.right != null) {
    
23.             TreeNode right = root.right;
    
24.             convertToDoubleLinkedList(right);
    
25.             while (right.left != null) {
    
26.                 right = right.left;
    
27.             }
    
28.             right.left = root;
    
29.             root.right = right;
    
30.         }
    
31.     }
    
32.    
    
33.     public void test(String[] args) {
    
34.         TreeNode a = new TreeNode("10");
    
35.         TreeNode b = new TreeNode("12");
    
36.         TreeNode c = new TreeNode("15");
    
37.         TreeNode d = new TreeNode("25");
    
38.         TreeNode e = new TreeNode("30");
    
39.         TreeNode f = new TreeNode("36");
    
40.         a.left = b;
    
41.         a.right = c;
    
42.         b.left = d;
    
43.         b.right = e;
    
44.         c.left = f;
    
45.         solve(a);
    
46.         while (a.left != null) {
    
47.             a = a.left;
    
48.         }
    
49.         while (a != null) {
    
50.             System.out.print(a.val + " ");
    
51.             a = a.right;
    
52.         }      
    
53.     }
    
54. }

复制代码

pandafolk 发表于 2015-3-19 08:51
oops，没贴上

谢谢啊！你从哪找的啊？

yuruofeifei 发表于 2015-3-18 22:53
谢谢啊！你从哪找的啊？

自己写的。。

个人感觉，楼上解法mix了recursive solution，和iterative solution，不够简明。

我的iterative solution with stack，其实就是一个中序遍历：

  public TreeNode BT2CircularDLL(TreeNode root) {
    if (root == null) {
      return root;
    }
    Stack<TreeNode> st = new Stack<>();
    TreeNode curr = root;
    TreeNode head = null;
    TreeNode tail = null;
    TreeNode prev = null;
    while (curr != null || !st.isEmpty()) {
      if (curr != null) {
        st.push(curr);
        curr = curr.left;
      } else {
        TreeNode popped = st.pop();
        if (prev != null) {
          prev.right = popped;
          popped.left = prev;
        } else {
          head = popped;
        }
        prev = popped;
        tail = popped;
        curr = popped.right;
      }
    }
    tail.right = head;
    head.left = tail;
    return head;
  }

你面的是intern还是fulltime呀？intern和full time的题目可能会一样吗？