由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字 访问原贴
JobHunting版 - fb家面试题讨论
相关主题
● 问一个leetcode上Validate Binary Search Tree的问题● 树 inorder下个节点最好办法是啥
● Find the node with given value in binary tree in in-order● [leetcode] Binary Tree from Inorder & Postorder Traversal
● leetcode的ＯＪ也会有错吗？？● 狗店面，求BLESS
● 这个inorder traversal 有错嘛，为什么leetcode 总报memory limit exceed?● 讨论几道google题（附个人答案）
● 回馈本版，新鲜店面，新题新气象● Construct Binary Tree from Preorder and Inorder Traversal算法复杂度？
● L 家面试高频题, 怎么解● 大牛帮我看看这哪错了? iterative inorder traversal
● 一道msft的题● inorder traversal的空间复杂度是O(N) 还是O(logN)?
● ms面试题● 这道题如何得到最优解
相关话题的讨论汇总
话题: treenode话题: tail话题: null话题: head话题: current
进入JobHunting版参与讨论
1 (共1页)
r******j
发帖数: 92
1
给一个binary tree，返回一个circular doubly-linked list。
不好意思，忘说了，按inorder返回。
S***w
发帖数: 1014
2
详细点？

【在 r******j 的大作中提到】
: 给一个binary tree，返回一个circular doubly-linked list。
: 不好意思，忘说了，按inorder返回。
h**d
发帖数: 630
3
什么order?
recursion传一个previous_node
根据题目要求的order traverse
每次把current_node->prev指向previous_node,previous_node->next指向current_
node

【在 r******j 的大作中提到】
: 给一个binary tree，返回一个circular doubly-linked list。
: 不好意思，忘说了，按inorder返回。
s**********r
发帖数: 88
4
这题不是F家经典题吗。网上很多了。
t**r
发帖数: 3428
5
如何 circular？
不太懂啊。
I**********s
发帖数: 441
6
简单:
TreeNode * convert(TreeNode * root) {
if (! root) return NULL;
TreeNode * head = NULL, * tail = NULL;
stack s;
TreeNode * n = root;
while (1) {
while (n) {
s.push(n);
n = n->left;
}
if (s.empty()) {
if (head) {
head->left = tail;
tail->right = head;
}
break;
}
else {
TreeNode * tmp = s.top();
s.pop();
n = tmp->right;

cout << tmp->val << endl;
append(tmp, head, tail);
}
}

return head;
}
void append(TreeNode * t, TreeNode *& head, TreeNode *& tail) {
if (head == NULL) {
head = tail = t;
t->left = t->right = NULL;
}
else {
tail->right = t;
t->left = tail;
t->right = NULL;
tail = t;
}
}
r******j
发帖数: 92
7
感觉java不能这么搞。按值传参，给pre新的reference没用。

【在 h**d 的大作中提到】
: 什么order?
: recursion传一个previous_node
: 根据题目要求的order traverse
: 每次把current_node->prev指向previous_node,previous_node->next指向current_
: node
z***m
发帖数: 1602
8
先生成DLL，然后把头尾相连

【在 t**r 的大作中提到】
: 如何 circular？
: 不太懂啊。
r******j
发帖数: 92
9
没有看到比较好的java solution呢。

【在 s**********r 的大作中提到】
: 这题不是F家经典题吗。网上很多了。
r******j
发帖数: 92
10
可以用recursion，不用stack吗？

【在 I**********s 的大作中提到】
: 简单:
: TreeNode * convert(TreeNode * root) {
: if (! root) return NULL;
: TreeNode * head = NULL, * tail = NULL;
: stack s;
: TreeNode * n = root;
: while (1) {
: while (n) {
: s.push(n);
: n = n->left;
相关主题
● L 家面试高频题, 怎么解● 树 inorder下个节点最好办法是啥
● 一道msft的题● [leetcode] Binary Tree from Inorder & Postorder Traversal
● ms面试题● 狗店面，求BLESS
进入JobHunting版参与讨论
r******j
发帖数: 92
11
可以用recursion，不用stack吗？感觉stack的解法不太好理解。。。

【在 I**********s 的大作中提到】
: 简单:
: TreeNode * convert(TreeNode * root) {
: if (! root) return NULL;
: TreeNode * head = NULL, * tail = NULL;
: stack s;
: TreeNode * n = root;
: while (1) {
: while (n) {
: s.push(n);
: n = n->left;
I**********s
发帖数: 441
12
用stack的是根据Binary Tree的iterative inorder traversal.
Recursive 版本如下：
TreeNode * convert(TreeNode * root) {
if (! root) return NULL;
TreeNode * head = NULL, * tail = NULL, * prev = NULL;
get(root, head, tail, prev);
if (head) {
head->left = tail;
tail->right = head;
}
return head;
}
void get(TreeNode * root, TreeNode *& head, TreeNode *& tail, TreeNode *
& prev) {
if (! root) return;
get(root->left, head, tail, prev);
if (! prev) {
head = tail = root;
}
else {
tail->right = root;
root->left = tail;
tail = root;
}
prev = root;
get(root->right, head, tail, prev);
}

【在 r******j 的大作中提到】
: 可以用recursion，不用stack吗？感觉stack的解法不太好理解。。。
r****7
发帖数: 2282
13
leetcode上就有吧，inorder visit，把prev->right设置成cur，cur->left = prev，
然后在prev = NULL的时候设置curr为head，不停的将head->left设置为cur

【在 r******j 的大作中提到】
: 给一个binary tree，返回一个circular doubly-linked list。
: 不好意思，忘说了，按inorder返回。
r******j
发帖数: 92
14
恩，是，用stack其实就是binary tree的iterative inorder traversal，但是觉得很
难解释这个解法，很难想到，能写出来也是半背半写的。恩你的recursive版本我明白
，可是在java里怎么给pre赋值没用吧。请指教。

【在 I**********s 的大作中提到】
: 用stack的是根据Binary Tree的iterative inorder traversal.
: Recursive 版本如下：
: TreeNode * convert(TreeNode * root) {
: if (! root) return NULL;
: TreeNode * head = NULL, * tail = NULL, * prev = NULL;
: get(root, head, tail, prev);
: if (head) {
: head->left = tail;
: tail->right = head;
: }
I**********s
发帖数: 441
15
java里prev, head, tail改成class member variable.

【在 r******j 的大作中提到】
: 恩，是，用stack其实就是binary tree的iterative inorder traversal，但是觉得很
: 难解释这个解法，很难想到，能写出来也是半背半写的。恩你的recursive版本我明白
: ，可是在java里怎么给pre赋值没用吧。请指教。
j**7
发帖数: 143
16
O(N) time, O(1) extra space
public TreeNode[] convertBST(TreeNode root) {
TreeNode head = null;
TreeNode tail = null;
TreeNode current = root;
while (current != null) {
if (current.left != null && current.left.value < current.value) {
TreeNode left = current.left;
while (left.right != null && left.right != current) {
left = left.right;
}
if (left.right == null) {
left.right = current;
current = current.left;
} else {
System.out.println(current.value);
if (head == null) {
head = current;
tail = current;
} else {
tail.right = current;
current.left = tail;
tail = current;
}
current = current.right;
}
} else {
System.out.println(current.value);
if (head == null) {
head = current;
tail = current;
} else {
tail.right = current;
current.left = tail;
tail = current;
}
current = current.right;
}
}
TreeNode[] result = new TreeNode[2];
result[0] = head;
result[1] = tail;
return result;
}
r******j
发帖数: 92
17
给一个binary tree，返回一个circular doubly-linked list。
不好意思，忘说了，按inorder返回。
S***w
发帖数: 1014
18
详细点？

【在 r******j 的大作中提到】
: 给一个binary tree，返回一个circular doubly-linked list。
: 不好意思，忘说了，按inorder返回。
h**d
发帖数: 630
19
什么order?
recursion传一个previous_node
根据题目要求的order traverse
每次把current_node->prev指向previous_node,previous_node->next指向current_
node

【在 r******j 的大作中提到】
: 给一个binary tree，返回一个circular doubly-linked list。
: 不好意思，忘说了，按inorder返回。
s**********r
发帖数: 88
20
这题不是F家经典题吗。网上很多了。
相关主题
● 讨论几道google题（附个人答案）● inorder traversal的空间复杂度是O(N) 还是O(logN)?
● Construct Binary Tree from Preorder and Inorder Traversal算法复杂度？● 这道题如何得到最优解
● 大牛帮我看看这哪错了? iterative inorder traversal● 树中序遍历，要求左子树用递归，右子树用iteration
进入JobHunting版参与讨论
t**r
发帖数: 3428
21
如何 circular？
不太懂啊。
I**********s
发帖数: 441
22
简单:
TreeNode * convert(TreeNode * root) {
if (! root) return NULL;
TreeNode * head = NULL, * tail = NULL;
stack s;
TreeNode * n = root;
while (1) {
while (n) {
s.push(n);
n = n->left;
}
if (s.empty()) {
if (head) {
head->left = tail;
tail->right = head;
}
break;
}
else {
TreeNode * tmp = s.top();
s.pop();
n = tmp->right;

cout << tmp->val << endl;
append(tmp, head, tail);
}
}

return head;
}
void append(TreeNode * t, TreeNode *& head, TreeNode *& tail) {
if (head == NULL) {
head = tail = t;
t->left = t->right = NULL;
}
else {
tail->right = t;
t->left = tail;
t->right = NULL;
tail = t;
}
}
r******j
发帖数: 92
23
感觉java不能这么搞。按值传参，给pre新的reference没用。

【在 h**d 的大作中提到】
: 什么order?
: recursion传一个previous_node
: 根据题目要求的order traverse
: 每次把current_node->prev指向previous_node,previous_node->next指向current_
: node
z***m
发帖数: 1602
24
先生成DLL，然后把头尾相连

【在 t**r 的大作中提到】
: 如何 circular？
: 不太懂啊。
r******j
发帖数: 92
25
没有看到比较好的java solution呢。

【在 s**********r 的大作中提到】
: 这题不是F家经典题吗。网上很多了。
r******j
发帖数: 92
26
可以用recursion，不用stack吗？

【在 I**********s 的大作中提到】
: 简单:
: TreeNode * convert(TreeNode * root) {
: if (! root) return NULL;
: TreeNode * head = NULL, * tail = NULL;
: stack s;
: TreeNode * n = root;
: while (1) {
: while (n) {
: s.push(n);
: n = n->left;
r******j
发帖数: 92
27
可以用recursion，不用stack吗？感觉stack的解法不太好理解。。。

【在 I**********s 的大作中提到】
: 简单:
: TreeNode * convert(TreeNode * root) {
: if (! root) return NULL;
: TreeNode * head = NULL, * tail = NULL;
: stack s;
: TreeNode * n = root;
: while (1) {
: while (n) {
: s.push(n);
: n = n->left;
I**********s
发帖数: 441
28
用stack的是根据Binary Tree的iterative inorder traversal.
Recursive 版本如下：
TreeNode * convert(TreeNode * root) {
if (! root) return NULL;
TreeNode * head = NULL, * tail = NULL, * prev = NULL;
get(root, head, tail, prev);
if (head) {
head->left = tail;
tail->right = head;
}
return head;
}
void get(TreeNode * root, TreeNode *& head, TreeNode *& tail, TreeNode *
& prev) {
if (! root) return;
get(root->left, head, tail, prev);
if (! prev) {
head = tail = root;
}
else {
tail->right = root;
root->left = tail;
tail = root;
}
prev = root;
get(root->right, head, tail, prev);
}

【在 r******j 的大作中提到】
: 可以用recursion，不用stack吗？感觉stack的解法不太好理解。。。
r****7
发帖数: 2282
29
leetcode上就有吧，inorder visit，把prev->right设置成cur，cur->left = prev，
然后在prev = NULL的时候设置curr为head，不停的将head->left设置为cur

【在 r******j 的大作中提到】
: 给一个binary tree，返回一个circular doubly-linked list。
: 不好意思，忘说了，按inorder返回。
r******j
发帖数: 92
30
恩，是，用stack其实就是binary tree的iterative inorder traversal，但是觉得很
难解释这个解法，很难想到，能写出来也是半背半写的。恩你的recursive版本我明白
，可是在java里怎么给pre赋值没用吧。请指教。

【在 I**********s 的大作中提到】
: 用stack的是根据Binary Tree的iterative inorder traversal.
: Recursive 版本如下：
: TreeNode * convert(TreeNode * root) {
: if (! root) return NULL;
: TreeNode * head = NULL, * tail = NULL, * prev = NULL;
: get(root, head, tail, prev);
: if (head) {
: head->left = tail;
: tail->right = head;
: }
相关主题
● 大概说一下昨天的Google Phone Interview● Find the node with given value in binary tree in in-order
● 讨论一道leetcode上面的题● leetcode的ＯＪ也会有错吗？？
● 问一个leetcode上Validate Binary Search Tree的问题● 这个inorder traversal 有错嘛，为什么leetcode 总报memory limit exceed?
进入JobHunting版参与讨论
I**********s
发帖数: 441
31
java里prev, head, tail改成class member variable.

【在 r******j 的大作中提到】
: 恩，是，用stack其实就是binary tree的iterative inorder traversal，但是觉得很
: 难解释这个解法，很难想到，能写出来也是半背半写的。恩你的recursive版本我明白
: ，可是在java里怎么给pre赋值没用吧。请指教。
j**7
发帖数: 143
32
O(N) time, O(1) extra space
public TreeNode[] convertBST(TreeNode root) {
TreeNode head = null;
TreeNode tail = null;
TreeNode current = root;
while (current != null) {
if (current.left != null && current.left.value < current.value) {
TreeNode left = current.left;
while (left.right != null && left.right != current) {
left = left.right;
}
if (left.right == null) {
left.right = current;
current = current.left;
} else {
System.out.println(current.value);
if (head == null) {
head = current;
tail = current;
} else {
tail.right = current;
current.left = tail;
tail = current;
}
current = current.right;
}
} else {
System.out.println(current.value);
if (head == null) {
head = current;
tail = current;
} else {
tail.right = current;
current.left = tail;
tail = current;
}
current = current.right;
}
}
TreeNode[] result = new TreeNode[2];
result[0] = head;
result[1] = tail;
return result;
}
t******5
发帖数: 30
33
mark
y*****e
发帖数: 712
34
根据前面的讨论写了个java的recursive的版本，iterative的再去想想，请大家指正
public class bt_circular_list{
private static TreeNode tail = null;
public static TreeNode convert(TreeNode root){
TreeNode head = root;
helper(root);
while(head.left != null){
head = head.left;
}
head.left = tail;
tail.right = head;
return head;
}

public static void helper(TreeNode root) {
if(root == null)
return;
helper(root.left);
if(tail != null){
tail.right = root;
root.left = tail;
}
tail = root;
helper(root.right);
}
}
e***a
发帖数: 1661
35
class Solution {
private DLNode head = null, dlnode = null;
private void bt2dll(TreeNode tnode) {
if (tnode == null) return null;
bt2dll(tnode.left);
if (dlnode == null) {
dlnode = new DLNode(tnode.val);
head = dlnode;
} else {
dlnode.next = new DLNode(tnode.val);
dlnode.next.prev = dlnode;
dlnode = dlnode.next;
}
bt2dll(tnode.right);
}
public DLNode start(TreeNode tnode) {
bt2dll(tnode);
if (head != null) {
head.prev = dlnode;
dlnode.next = head;
}
return head;
}
}
f******n
发帖数: 198
36
最后忘记连成环了吧。

【在 e***a 的大作中提到】
: class Solution {
: private DLNode head = null, dlnode = null;
: private void bt2dll(TreeNode tnode) {
: if (tnode == null) return null;
: bt2dll(tnode.left);
: if (dlnode == null) {
: dlnode = new DLNode(tnode.val);
: head = dlnode;
: } else {
: dlnode.next = new DLNode(tnode.val);
s*********3
发帖数: 25
37
我也面了这题，我答的挺好的，结果挂了。

【在 r******j 的大作中提到】
: 给一个binary tree，返回一个circular doubly-linked list。
: 不好意思，忘说了，按inorder返回。
r******j
发帖数: 92
38
你是怎么答的？recursion还是stack？

【在 s*********3 的大作中提到】
: 我也面了这题，我答的挺好的，结果挂了。
1 (共1页)
进入JobHunting版参与讨论
相关主题
● 这道题如何得到最优解● 回馈本版，新鲜店面，新题新气象
● 树中序遍历，要求左子树用递归，右子树用iteration● L 家面试高频题, 怎么解
● 大概说一下昨天的Google Phone Interview● 一道msft的题
● 讨论一道leetcode上面的题● ms面试题
● 问一个leetcode上Validate Binary Search Tree的问题● 树 inorder下个节点最好办法是啥
● Find the node with given value in binary tree in in-order● [leetcode] Binary Tree from Inorder & Postorder Traversal
● leetcode的ＯＪ也会有错吗？？● 狗店面，求BLESS
● 这个inorder traversal 有错嘛，为什么leetcode 总报memory limit exceed?● 讨论几道google题（附个人答案）
相关话题的讨论汇总
话题: treenode话题: tail话题: null话题: head话题: current

未名新帖统计// 7月16日

#版面帖数(主题数)
-全站4871 (796)
1Military3777 (569)
2Stock341 (51)
3Joke117 (17)
4History116 (3)
5Automobile100 (9)
6USANews55 (9)
7Midlife45 (1)
8Headline41 (41)
9Dreamer33 (13)
10FleaMarket32 (20)
11Living30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)

历史上的今天

  1. faintcat妹妹看进来～～ 发表于12年前.
  2. NSC, PD 1/7/2007, EB2, ... 发表于11年前.
  3. [FBA求购]MJVE2 758 MJVM2 ... 发表于6年前.
  4. 老生常谈,归与不归 发表于10年前.
  5. 【申请】Seattle西雅图 版版主——申请人... 发表于9年前.
  6. 宝宝出生，头骨骨折，求祝福 发表于9年前.
  7. 求推荐舒缓优美的古典音乐 发表于11年前.
  8. 百分之一的北京人上北大 中国网友愤怒(转载） 发表于10年前.
  9. 新人带狗狗Bailey来报道 发表于12年前.
  10. 全世界最有价值的运动队 发表于10年前.
  11. 请问大切诺基的质量如何 发表于6年前.
  12. TNND，军版全是BKC 发表于15年前.
  13. Inception 发表于12年前.
  14. 微软的有些家属可真恶心，为了卖保险脸都不要了 发表于10年前.
  15. 每周坐高铁的苦逼来说说感受吧!! 发表于9年前.
除非另有声明，本站内容采用Creative Commons BY-NC-SA 3.0协议进行许可，转载请注明来自未名观察 - 隐私政策2011-07-24 10:06:12由admin编辑