e******i
发帖数: 106 | 1 Hi leetcode上我有道题看不明白，求教各位大神。
是关于flatten binary tree to linkedlist那道。
我看到一个答案。
public class Solution {
03 public void flatten(TreeNode root) {
04 if(root==null)
05 return;
06
07 TreeNode curr=null;
08 Stack trees=new Stack();
09 trees.add(root);
10 while(!trees.empty())
11 {
12 TreeNode parent=trees.pop();
13
14 if(parent.right!=null)
15 {
16 trees.push(parent.right);
17 }
18
19 if(parent.left!=null)
20 {
21 trees.push(parent.left);
22 }
23 parent.left=null;
24 parent.right=null;
25 if(root==parent)
26 {
27 curr=parent;
28 }
29 else
30 {
31 curr.right=parent;
32 curr=curr.right;
33 }
34 }
35
36 }
37 }
这个答案是能通过测试的。
可是我看不懂的地方是除了在12行，将stack里的root节点赋值给parent意外，自始至
终root节点都没有改变过。为什么root就被flatten了呢？
我太水了，真心看不懂 |
c*****a
发帖数: 808 | 2 while()前半是preorder-traverse
后半段这里就是连接部份
31 curr.right=parent;
32 curr=curr.right;
你把名字parent改为curr, curr改为prev这样的容易明白了 |
l*******b
发帖数: 2586 | 3 贴个我写的。。。
void flatten2(TreeNode *r) { // In place way
while(r) {
if(r->right == NULL) {
r->right = r->left;
r->left = NULL; // leetcode require this
} else if(r->left != NULL) {
TreeNode *t = r->left;
while(t->right)
t = t->right;
t->right = r->right;
r->right = r->left;
r->left = NULL; // leetcode require this
}
r = r->right;
}
} |
c********t
发帖数: 5706 | 4 root没有变，parent和curr在变，把所有节点都flatten到root->right了。
唯一我觉得奇怪的是，curr和parent似乎应该exchange才配得上名字。
可以先试试写recursion的。
【在 e******i 的大作中提到】
: Hi leetcode上我有道题看不明白，求教各位大神。
: 是关于flatten binary tree to linkedlist那道。
: 我看到一个答案。
: public class Solution {
: 03 public void flatten(TreeNode root) {
: 04 if(root==null)
: 05 return;
: 06
: 07 TreeNode curr=null;
: 08 Stack trees=new Stack();
|
c********t
发帖数: 5706 | 5 太赞了
【在 l*******b 的大作中提到】
: 贴个我写的。。。
: void flatten2(TreeNode *r) { // In place way
: while(r) {
: if(r->right == NULL) {
: r->right = r->left;
: r->left = NULL; // leetcode require this
: } else if(r->left != NULL) {
: TreeNode *t = r->left;
: while(t->right)
: t = t->right;
|
p*****2
发帖数: 21240 | 6 这道题我不明白为什么最后转成了单链表。难道不应该是双链表吗？CC150上的原题。
单链表貌似简单了。 |
l*******b
发帖数: 2586 | 7 有了单链表，再遍历一遍到双链表就是了吧？
【在 p*****2 的大作中提到】
: 这道题我不明白为什么最后转成了单链表。难道不应该是双链表吗？CC150上的原题。
: 单链表貌似简单了。
|
p*****2
发帖数: 21240 | 8
你可以试试只扫一遍。
【在 l*******b 的大作中提到】
: 有了单链表，再遍历一遍到双链表就是了吧？
|
l*******b
发帖数: 2586 | 9 嗯，加个指针p，在递归到下一层时把r存下来就可以了
开始加一个
TreeNode *p = NULL;
最后一段改成：
r->left = p;
p = r;
r = r->right;
【在 p*****2 的大作中提到】
:
: 你可以试试只扫一遍。
|
c********t
发帖数: 5706 | 10 似乎可行
记得有一个题是bstin-place 转成从小到大的double linked list.有空做做看。
【在 l*******b 的大作中提到】
: 嗯，加个指针p，在递归到下一层时把r存下来就可以了
: 开始加一个
: TreeNode *p = NULL;
: 最后一段改成：
: r->left = p;
: p = r;
: r = r->right;
|
e******i
发帖数: 106 | 11
哈哈，大神说的果然通俗易懂，我明白了。
谢谢！
【在 c*****a 的大作中提到】
: while()前半是preorder-traverse
: 后半段这里就是连接部份
: 31 curr.right=parent;
: 32 curr=curr.right;
: 你把名字parent改为curr, curr改为prev这样的容易明白了
|
p*g
发帖数: 141 | 12 public void flatten(TreeNode root) {
flat(root);
}
public TreeNode flat(TreeNode root) {
if (root==null) return null;
TreeNode rv = root;
TreeNode rt = root.right;
root.right = flat(root.left);
root.left = null;
while (root.right!=null) root = root.right;
root.right = flat(rt);
return rv;
}
【在 e******i 的大作中提到】
: Hi leetcode上我有道题看不明白，求教各位大神。
: 是关于flatten binary tree to linkedlist那道。
: 我看到一个答案。
: public class Solution {
: 03 public void flatten(TreeNode root) {
: 04 if(root==null)
: 05 return;
: 06
: 07 TreeNode curr=null;
: 08 Stack trees=new Stack();
|
