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 | |
t**r 发帖数: 3428 | |
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;
|
|
|
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 | |
|
|
t**r 发帖数: 3428 | |
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; : }
|
|
|
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 | |
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 的大作中提到】 : 我也面了这题,我答的挺好的,结果挂了。
|