Facebook 11.2 intern一轮面试

xiaozhuxiaozhu 发表于 2016-11-3 06:38
lz方便第2题，贴个代码么，非常感谢。

void treeToDoublyList(Node *p, Node *& prev, Node *& head) {
  if (!p) return;
  treeToDoublyList(p->left, prev, head);
  p->left = prev;
  if (prev)
    prev->right = p;
  else
    head = p;
  Node *right = p->right;
  head->left = p;
  p->right = head;
  prev = p;
  treeToDoublyList(right, prev, head);
}


Node* treeToDoublyList(Node *root) {
  Node *prev = NULL;
  Node *head = NULL;
  treeToDoublyList(root, prev, head);
  return head;
}

Badger96 发表于 2016-11-3 06:57
也只有Morris Traversal能做到O(1)空间了吧。。

其实就是convert in place

tkw1110 发表于 2016-11-3 11:32
其实就是convert in place

可是你这样递归不是用了stack space么？不算O(1)空间复杂度吧

明白了，楼主的意思是要inplace修改成ddl，不过用递归并不是O(1)空间。。

Badger96 发表于 2016-11-3 12:03
明白了，楼主的意思是要inplace修改成ddl，不过用递归并不是O(1)空间。。

嗯嗯，对。是我表达的问题，抱歉

geeksforgeeks.org/in-place-convert-a-given-binary-tree-to-doubly-linked-list/ 一样吧？

xxxxx56789 发表于 2016-11-3 14:37
geeksforgeeks.org/in-place-convert-a-given-binary-tree-to-doubly-linked-list/ 一样吧？

对，就是这个

他给你的估计是 据+很确定。所以你就被据了，和bar没什么关系。如果他给你一个过+不确定，你都可以继续下一轮的。当然这是我猜的，估计小哥比较心黑吧。

honghunan 发表于 2016-11-4 23:51
他给你的估计是 据+很确定。所以你就被据了，和bar没什么关系。如果他给你一个过+不确定，你都可以继续下一 ...

哎，真不知道什么鬼，明明都bug free了。很不开心

tkw1110 发表于 2016-11-5 02:00
哎，真不知道什么鬼，明明都bug free了。很不开心

表担心，好公司还很多呢！！加油！！勤奋会有回报的！