四大名著新解# Joke - 肚皮舞运动
j*2
1 楼
Given preorder of a binary tree, generate all the possible binary trees.
Note that it is not necessarily a binary search tree.
Note that it is not necessarily a binary search tree.
e*e
2 楼
多谢
f*e
3 楼
1、红楼：大部分是女人；水浒：大部分是男人；西游：大部分不是人；三国：大部分
全是人。2、红楼：丫头脸皮厚；水浒：朝廷脸皮厚； 三国：军师脸皮厚；西游：神仙
脸皮厚。3、 西游：猴哥救我 ；红楼：妹妹救我；水浒：叔叔救我；三国：军师救我。
全是人。2、红楼：丫头脸皮厚；水浒：朝廷脸皮厚； 三国：军师脸皮厚；西游：神仙
脸皮厚。3、 西游：猴哥救我 ；红楼：妹妹救我；水浒：叔叔救我；三国：军师救我。
g*e
4 楼
递归
【在 j********2 的大作中提到】
: Given preorder of a binary tree, generate all the possible binary trees.
: Note that it is not necessarily a binary search tree.
【在 j********2 的大作中提到】
: Given preorder of a binary tree, generate all the possible binary trees.
: Note that it is not necessarily a binary search tree.
b*r
5 楼
个人感觉按照年代顺序放就行了，已经不错了~
【在 e***e 的大作中提到】
: 多谢
【在 e***e 的大作中提到】
: 多谢
r*e
6 楼
不错!!
我。
【在 f**e 的大作中提到】
: 1、红楼：大部分是女人；水浒：大部分是男人；西游：大部分不是人；三国：大部分
: 全是人。2、红楼：丫头脸皮厚；水浒：朝廷脸皮厚； 三国：军师脸皮厚；西游：神仙
: 脸皮厚。3、 西游：猴哥救我 ；红楼：妹妹救我；水浒：叔叔救我；三国：军师救我。
我。
【在 f**e 的大作中提到】
: 1、红楼：大部分是女人；水浒：大部分是男人；西游：大部分不是人；三国：大部分
: 全是人。2、红楼：丫头脸皮厚；水浒：朝廷脸皮厚； 三国：军师脸皮厚；西游：神仙
: 脸皮厚。3、 西游：猴哥救我 ；红楼：妹妹救我；水浒：叔叔救我；三国：军师救我。
g*y
7 楼
This one is too easy, not interesting.
Try this one, which is more interesting (and difficult):
Given pre-order and post-order sequences of {string node_value, bool is_leaf
} of a GENERAL tree, reconstruct the tree, HOWEVER, "node_value" CANNOT be
used to identify a node (i.e., there could be duplicate node values).
【在 j********2 的大作中提到】
: Given preorder of a binary tree, generate all the possible binary trees.
: Note that it is not necessarily a binary search tree.
Try this one, which is more interesting (and difficult):
Given pre-order and post-order sequences of {string node_value, bool is_leaf
} of a GENERAL tree, reconstruct the tree, HOWEVER, "node_value" CANNOT be
used to identify a node (i.e., there could be duplicate node values).
【在 j********2 的大作中提到】
: Given preorder of a binary tree, generate all the possible binary trees.
: Note that it is not necessarily a binary search tree.
b*n
8 楼
水浒：叔叔救我？
j*2
9 楼
大牛贴个代码吧
leaf
【在 g*******y 的大作中提到】
: This one is too easy, not interesting.
: Try this one, which is more interesting (and difficult):
: Given pre-order and post-order sequences of {string node_value, bool is_leaf
: } of a GENERAL tree, reconstruct the tree, HOWEVER, "node_value" CANNOT be
: used to identify a node (i.e., there could be duplicate node values).
leaf
【在 g*******y 的大作中提到】
: This one is too easy, not interesting.
: Try this one, which is more interesting (and difficult):
: Given pre-order and post-order sequences of {string node_value, bool is_leaf
: } of a GENERAL tree, reconstruct the tree, HOWEVER, "node_value" CANNOT be
: used to identify a node (i.e., there could be duplicate node values).
s*l
10 楼
想想看，金莲姐姐的叔叔是谁。
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 b*****n 的大作中提到】
: 水浒：叔叔救我？
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 b*****n 的大作中提到】
: 水浒：叔叔救我？
z*g
11 楼
我正好做过一个讲解视频 http://www.youtube.com/watch?v=rvMOG_yKBA0
java的代码在这里：https://dl.dropbox.com/u/14935294/ProgrammingVideos/44-Get
_All_Possible_In_Orders_From_Pre_Order_Traversal/GetAllInOrdersFromPreOrder.
java
java的代码在这里：https://dl.dropbox.com/u/14935294/ProgrammingVideos/44-Get
_All_Possible_In_Orders_From_Pre_Order_Traversal/GetAllInOrdersFromPreOrder.
java
R*a
12 楼
金莲姐姐的叔叔为啥要救她？
【在 s****l 的大作中提到】
: 想想看，金莲姐姐的叔叔是谁。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 s****l 的大作中提到】
: 想想看，金莲姐姐的叔叔是谁。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
Z*Z
13 楼
膜拜啊，好久不见这位神牛了，要往FB跳马？：）
我来抛砖引玉一下吧。我认为从先序、后序重构树，和只从先序重构树，的算法差不多
。
假设输入preList[1...N]和postList[1...N]分别代表先序和后序遍历的结果。
可以把先序遍历的第一个节点preList[1]当做根，剩下的的节点分成连续的两部分，pr
eList[2,i], preList[i+1,N]（i = 1...N)，然后分别重构左、右子树。最后再把左右
子树交叉合并起来。
以第一次划分为例，对于i从1到N时的两个子问题分别为：
preList[2...i], postList[1,i-1]
preList[i+1...N], postList[i,N-1]
任何一个子问题都有可能没有解。原因是：
(1)把preList[...]和postList[...]看成集合，他们含有不同的元素
(2)preList的第一个元素和postList的最后一个元素不相同
这个时候这个子问题的划分本身就是invalid的，可以skip
然后问题可能有多个解，那个is_leaf的flag并没有消除解的歧义性。考虑到一棵退化成
一条线的树，所有节点有相同的node_value，那么重构的结果有2^(N-1)种可能性。所以
算法的复杂度也是指数级的。
leaf
【在 g*******y 的大作中提到】
: This one is too easy, not interesting.
: Try this one, which is more interesting (and difficult):
: Given pre-order and post-order sequences of {string node_value, bool is_leaf
: } of a GENERAL tree, reconstruct the tree, HOWEVER, "node_value" CANNOT be
: used to identify a node (i.e., there could be duplicate node values).
我来抛砖引玉一下吧。我认为从先序、后序重构树，和只从先序重构树，的算法差不多
。
假设输入preList[1...N]和postList[1...N]分别代表先序和后序遍历的结果。
可以把先序遍历的第一个节点preList[1]当做根，剩下的的节点分成连续的两部分，pr
eList[2,i], preList[i+1,N]（i = 1...N)，然后分别重构左、右子树。最后再把左右
子树交叉合并起来。
以第一次划分为例，对于i从1到N时的两个子问题分别为：
preList[2...i], postList[1,i-1]
preList[i+1...N], postList[i,N-1]
任何一个子问题都有可能没有解。原因是：
(1)把preList[...]和postList[...]看成集合，他们含有不同的元素
(2)preList的第一个元素和postList的最后一个元素不相同
这个时候这个子问题的划分本身就是invalid的，可以skip
然后问题可能有多个解，那个is_leaf的flag并没有消除解的歧义性。考虑到一棵退化成
一条线的树，所有节点有相同的node_value，那么重构的结果有2^(N-1)种可能性。所以
算法的复杂度也是指数级的。
leaf
【在 g*******y 的大作中提到】
: This one is too easy, not interesting.
: Try this one, which is more interesting (and difficult):
: Given pre-order and post-order sequences of {string node_value, bool is_leaf
: } of a GENERAL tree, reconstruct the tree, HOWEVER, "node_value" CANNOT be
: used to identify a node (i.e., there could be duplicate node values).
b*n
14 楼
我也觉得奇怪，没这个场景啊
【在 R***a 的大作中提到】
: 金莲姐姐的叔叔为啥要救她？
【在 R***a 的大作中提到】
: 金莲姐姐的叔叔为啥要救她？
g*y
15 楼
不是不是，我就是顺路沾沾FB的名气post一道题目，嘿嘿
你题目可能没有理解好（或者我没有说足够清楚），所谓General tree，每个节点有一
个child list (sequential ordered children), 可以有0到任意多个children。所以
，general tree没有左孩子右孩子的notion，不存在左子树右子树的概念。
唉，我好歹还把general tree这个词大写了。。。
pr
【在 Z*****Z 的大作中提到】
: 膜拜啊，好久不见这位神牛了，要往FB跳马？：）
: 我来抛砖引玉一下吧。我认为从先序、后序重构树，和只从先序重构树，的算法差不多
: 。
: 假设输入preList[1...N]和postList[1...N]分别代表先序和后序遍历的结果。
: 可以把先序遍历的第一个节点preList[1]当做根，剩下的的节点分成连续的两部分，pr
: eList[2,i], preList[i+1,N]（i = 1...N)，然后分别重构左、右子树。最后再把左右
: 子树交叉合并起来。
: 以第一次划分为例，对于i从1到N时的两个子问题分别为：
: preList[2...i], postList[1,i-1]
: preList[i+1...N], postList[i,N-1]
你题目可能没有理解好（或者我没有说足够清楚），所谓General tree，每个节点有一
个child list (sequential ordered children), 可以有0到任意多个children。所以
，general tree没有左孩子右孩子的notion，不存在左子树右子树的概念。
唉，我好歹还把general tree这个词大写了。。。
pr
【在 Z*****Z 的大作中提到】
: 膜拜啊，好久不见这位神牛了，要往FB跳马？：）
: 我来抛砖引玉一下吧。我认为从先序、后序重构树，和只从先序重构树，的算法差不多
: 。
: 假设输入preList[1...N]和postList[1...N]分别代表先序和后序遍历的结果。
: 可以把先序遍历的第一个节点preList[1]当做根，剩下的的节点分成连续的两部分，pr
: eList[2,i], preList[i+1,N]（i = 1...N)，然后分别重构左、右子树。最后再把左右
: 子树交叉合并起来。
: 以第一次划分为例，对于i从1到N时的两个子问题分别为：
: preList[2...i], postList[1,i-1]
: preList[i+1...N], postList[i,N-1]
k*n
16 楼
小叔子。。
s*0
17 楼
那举个特例：二叉树
1 1
/ \
2 2
preorder: 1->2
postorder: 2->1
单单你给的条件ms不能保证unique啊， 我丢什么东西了么？
leaf
【在 g*******y 的大作中提到】
: This one is too easy, not interesting.
: Try this one, which is more interesting (and difficult):
: Given pre-order and post-order sequences of {string node_value, bool is_leaf
: } of a GENERAL tree, reconstruct the tree, HOWEVER, "node_value" CANNOT be
: used to identify a node (i.e., there could be duplicate node values).
1 1
/ \
2 2
preorder: 1->2
postorder: 2->1
单单你给的条件ms不能保证unique啊， 我丢什么东西了么？
leaf
【在 g*******y 的大作中提到】
: This one is too easy, not interesting.
: Try this one, which is more interesting (and difficult):
: Given pre-order and post-order sequences of {string node_value, bool is_leaf
: } of a GENERAL tree, reconstruct the tree, HOWEVER, "node_value" CANNOT be
: used to identify a node (i.e., there could be duplicate node values).
Z*Z
18 楼
其实注意到了你强调general tree，只不过之前觉得对于general tree来说没有inorde
r traversal，所以也想当然的没有inorder和preorder，这是不对的。Anyway，这样一
想很多东西就开始make sense了。问题貌似因此被简化了。
试着扩展我上面提到的方法。假定输入两个traversal的list：preList[1,N]和postLis
t[1,N]。从root节点来看，这两个list的组成其实是这样的：
preList [ rootNode, [child_1_root, ...], [child_2], ... [child_m] ]
postList[ [... child_1_root], [child_2], ... [child_m], rootNode
]
算法需要做的就是，把preList的第一个节点（也就是postList的最后一个节点）取出来
当做root，然后把剩下的preList和postList划分成若区间（代表若干子树），然后递归
调用自己。划分的方法是，用两个指针同时从前往后扫描两个list，找到一个划分区间
的条件是：
(1)这两个区间含有相同数目的相同节点
(2)preList区间的第一个节点等于postList区间的第二个节点
这里相同节点定义为两个节点的的node_value和is_leaf都相同。
题目还强调node_value不能identify一个节点，所以有可能需要回溯。。。
【在 g*******y 的大作中提到】
: 不是不是，我就是顺路沾沾FB的名气post一道题目，嘿嘿
: 你题目可能没有理解好（或者我没有说足够清楚），所谓General tree，每个节点有一
: 个child list (sequential ordered children), 可以有0到任意多个children。所以
: ，general tree没有左孩子右孩子的notion，不存在左子树右子树的概念。
: 唉，我好歹还把general tree这个词大写了。。。
:
: pr
r traversal，所以也想当然的没有inorder和preorder，这是不对的。Anyway，这样一
想很多东西就开始make sense了。问题貌似因此被简化了。
试着扩展我上面提到的方法。假定输入两个traversal的list：preList[1,N]和postLis
t[1,N]。从root节点来看，这两个list的组成其实是这样的：
preList [ rootNode, [child_1_root, ...], [child_2], ... [child_m] ]
postList[ [... child_1_root], [child_2], ... [child_m], rootNode
]
算法需要做的就是，把preList的第一个节点（也就是postList的最后一个节点）取出来
当做root，然后把剩下的preList和postList划分成若区间（代表若干子树），然后递归
调用自己。划分的方法是，用两个指针同时从前往后扫描两个list，找到一个划分区间
的条件是：
(1)这两个区间含有相同数目的相同节点
(2)preList区间的第一个节点等于postList区间的第二个节点
这里相同节点定义为两个节点的的node_value和is_leaf都相同。
题目还强调node_value不能identify一个节点，所以有可能需要回溯。。。
【在 g*******y 的大作中提到】
: 不是不是，我就是顺路沾沾FB的名气post一道题目，嘿嘿
: 你题目可能没有理解好（或者我没有说足够清楚），所谓General tree，每个节点有一
: 个child list (sequential ordered children), 可以有0到任意多个children。所以
: ，general tree没有左孩子右孩子的notion，不存在左子树右子树的概念。
: 唉，我好歹还把general tree这个词大写了。。。
:
: pr
Z*Z
19 楼
他说的不是二叉树，所以没有左右子树的歧义性。你给的两棵树其实是一样的。
【在 s********0 的大作中提到】
: 那举个特例：二叉树
: 1 1
: / \
: 2 2
: preorder: 1->2
: postorder: 2->1
: 单单你给的条件ms不能保证unique啊， 我丢什么东西了么？
:
: leaf
【在 s********0 的大作中提到】
: 那举个特例：二叉树
: 1 1
: / \
: 2 2
: preorder: 1->2
: postorder: 2->1
: 单单你给的条件ms不能保证unique啊， 我丢什么东西了么？
:
: leaf
g*y
20 楼
这个思路很好，但是可惜不work（不敢肯定一定不work，至少狠不efficient），因为
要递归的话，你得知道［child_i_root］这个集合里的node的个数
要给提示么？还是再想想？我说个不算提示的提示吧，就是这个题目里面真正有用的
input只有bool is_leaf，那个string node_value完全是迷惑人的
inorde
postLis
rootNode
出来
递归
【在 Z*****Z 的大作中提到】
: 其实注意到了你强调general tree，只不过之前觉得对于general tree来说没有inorde
: r traversal，所以也想当然的没有inorder和preorder，这是不对的。Anyway，这样一
: 想很多东西就开始make sense了。问题貌似因此被简化了。
: 试着扩展我上面提到的方法。假定输入两个traversal的list：preList[1,N]和postLis
: t[1,N]。从root节点来看，这两个list的组成其实是这样的：
: preList [ rootNode, [child_1_root, ...], [child_2], ... [child_m] ]
: postList[ [... child_1_root], [child_2], ... [child_m], rootNode
: ]
: 算法需要做的就是，把preList的第一个节点（也就是postList的最后一个节点）取出来
: 当做root，然后把剩下的preList和postList划分成若区间（代表若干子树），然后递归
要递归的话，你得知道［child_i_root］这个集合里的node的个数
要给提示么？还是再想想？我说个不算提示的提示吧，就是这个题目里面真正有用的
input只有bool is_leaf，那个string node_value完全是迷惑人的
inorde
postLis
rootNode
出来
递归
【在 Z*****Z 的大作中提到】
: 其实注意到了你强调general tree，只不过之前觉得对于general tree来说没有inorde
: r traversal，所以也想当然的没有inorder和preorder，这是不对的。Anyway，这样一
: 想很多东西就开始make sense了。问题貌似因此被简化了。
: 试着扩展我上面提到的方法。假定输入两个traversal的list：preList[1,N]和postLis
: t[1,N]。从root节点来看，这两个list的组成其实是这样的：
: preList [ rootNode, [child_1_root, ...], [child_2], ... [child_m] ]
: postList[ [... child_1_root], [child_2], ... [child_m], rootNode
: ]
: 算法需要做的就是，把preList的第一个节点（也就是postList的最后一个节点）取出来
: 当做root，然后把剩下的preList和postList划分成若区间（代表若干子树），然后递归
Z*Z
21 楼
我想到啦，等我整理一下思路。
【在 g*******y 的大作中提到】
: 这个思路很好，但是可惜不work（不敢肯定一定不work，至少狠不efficient），因为
: 要递归的话，你得知道［child_i_root］这个集合里的node的个数
: 要给提示么？还是再想想？我说个不算提示的提示吧，就是这个题目里面真正有用的
: input只有bool is_leaf，那个string node_value完全是迷惑人的
:
: inorde
: postLis
: rootNode
: 出来
: 递归
【在 g*******y 的大作中提到】
: 这个思路很好，但是可惜不work（不敢肯定一定不work，至少狠不efficient），因为
: 要递归的话，你得知道［child_i_root］这个集合里的node的个数
: 要给提示么？还是再想想？我说个不算提示的提示吧，就是这个题目里面真正有用的
: input只有bool is_leaf，那个string node_value完全是迷惑人的
:
: inorde
: postLis
: rootNode
: 出来
: 递归
Z*Z
22 楼
The idea is to reconstruct the original tree while walking through it, using
the given sequences. We use pre-order sequence to traverse down, while usin
g post-order sequence to back out.
The reconstructed tree will be a general tree, meaning each internal node ca
n have arbitrary number of children. Also each node will have a parent point
er.
We need three pointers: treePtr, prePtr and postPtr that point to the curren
t tree node, pre-order sequence and post-order sequence, respectively. The r
oot is the first node of pre-order sequence, clearly. treePtr can be initial
ized to point to root.
Pseudo code:
while (prePtr != end)
do{
// advance prePtr
prePtr = next(prePtr);
// add a child to current tree node
// also update treePtr to point to the newly added child
treePtr = treePtr.addChild(prePtr);
} while(prePtr is not leaf);
do{
// traverse up the tree using post-order sequence
treePtr = treePtr.parent;
postPtr = next(postPtr);
} while(postPtr is not leaf);
}
leaf
【在 g*******y 的大作中提到】
: This one is too easy, not interesting.
: Try this one, which is more interesting (and difficult):
: Given pre-order and post-order sequences of {string node_value, bool is_leaf
: } of a GENERAL tree, reconstruct the tree, HOWEVER, "node_value" CANNOT be
: used to identify a node (i.e., there could be duplicate node values).
the given sequences. We use pre-order sequence to traverse down, while usin
g post-order sequence to back out.
The reconstructed tree will be a general tree, meaning each internal node ca
n have arbitrary number of children. Also each node will have a parent point
er.
We need three pointers: treePtr, prePtr and postPtr that point to the curren
t tree node, pre-order sequence and post-order sequence, respectively. The r
oot is the first node of pre-order sequence, clearly. treePtr can be initial
ized to point to root.
Pseudo code:
while (prePtr != end)
do{
// advance prePtr
prePtr = next(prePtr);
// add a child to current tree node
// also update treePtr to point to the newly added child
treePtr = treePtr.addChild(prePtr);
} while(prePtr is not leaf);
do{
// traverse up the tree using post-order sequence
treePtr = treePtr.parent;
postPtr = next(postPtr);
} while(postPtr is not leaf);
}
leaf
【在 g*******y 的大作中提到】
: This one is too easy, not interesting.
: Try this one, which is more interesting (and difficult):
: Given pre-order and post-order sequences of {string node_value, bool is_leaf
: } of a GENERAL tree, reconstruct the tree, HOWEVER, "node_value" CANNOT be
: used to identify a node (i.e., there could be duplicate node values).
c*x
23 楼
just maintain two multi-set, recurse to next layer when two multiset are
equal
leaf
【在 g*******y 的大作中提到】
: This one is too easy, not interesting.
: Try this one, which is more interesting (and difficult):
: Given pre-order and post-order sequences of {string node_value, bool is_leaf
: } of a GENERAL tree, reconstruct the tree, HOWEVER, "node_value" CANNOT be
: used to identify a node (i.e., there could be duplicate node values).
equal
leaf
【在 g*******y 的大作中提到】
: This one is too easy, not interesting.
: Try this one, which is more interesting (and difficult):
: Given pre-order and post-order sequences of {string node_value, bool is_leaf
: } of a GENERAL tree, reconstruct the tree, HOWEVER, "node_value" CANNOT be
: used to identify a node (i.e., there could be duplicate node values).
H*r
24 楼
听起来挺有意思，能给个example input吗？
leaf
【在 g*******y 的大作中提到】
: This one is too easy, not interesting.
: Try this one, which is more interesting (and difficult):
: Given pre-order and post-order sequences of {string node_value, bool is_leaf
: } of a GENERAL tree, reconstruct the tree, HOWEVER, "node_value" CANNOT be
: used to identify a node (i.e., there could be duplicate node values).
leaf
【在 g*******y 的大作中提到】
: This one is too easy, not interesting.
: Try this one, which is more interesting (and difficult):
: Given pre-order and post-order sequences of {string node_value, bool is_leaf
: } of a GENERAL tree, reconstruct the tree, HOWEVER, "node_value" CANNOT be
: used to identify a node (i.e., there could be duplicate node values).
H*r
25 楼
是说input是由真正的node组成而不是只有content?
【在 g*******y 的大作中提到】
: 这个思路很好，但是可惜不work（不敢肯定一定不work，至少狠不efficient），因为
: 要递归的话，你得知道［child_i_root］这个集合里的node的个数
: 要给提示么？还是再想想？我说个不算提示的提示吧，就是这个题目里面真正有用的
: input只有bool is_leaf，那个string node_value完全是迷惑人的
:
: inorde
: postLis
: rootNode
: 出来
: 递归
【在 g*******y 的大作中提到】
: 这个思路很好，但是可惜不work（不敢肯定一定不work，至少狠不efficient），因为
: 要递归的话，你得知道［child_i_root］这个集合里的node的个数
: 要给提示么？还是再想想？我说个不算提示的提示吧，就是这个题目里面真正有用的
: input只有bool is_leaf，那个string node_value完全是迷惑人的
:
: inorde
: postLis
: rootNode
: 出来
: 递归
b*g
26 楼
cool
using
usin
ca
point
curren
r
initial
【在 Z*****Z 的大作中提到】
: The idea is to reconstruct the original tree while walking through it, using
: the given sequences. We use pre-order sequence to traverse down, while usin
: g post-order sequence to back out.
: The reconstructed tree will be a general tree, meaning each internal node ca
: n have arbitrary number of children. Also each node will have a parent point
: er.
: We need three pointers: treePtr, prePtr and postPtr that point to the curren
: t tree node, pre-order sequence and post-order sequence, respectively. The r
: oot is the first node of pre-order sequence, clearly. treePtr can be initial
: ized to point to root.
using
usin
ca
point
curren
r
initial
【在 Z*****Z 的大作中提到】
: The idea is to reconstruct the original tree while walking through it, using
: the given sequences. We use pre-order sequence to traverse down, while usin
: g post-order sequence to back out.
: The reconstructed tree will be a general tree, meaning each internal node ca
: n have arbitrary number of children. Also each node will have a parent point
: er.
: We need three pointers: treePtr, prePtr and postPtr that point to the curren
: t tree node, pre-order sequence and post-order sequence, respectively. The r
: oot is the first node of pre-order sequence, clearly. treePtr can be initial
: ized to point to root.
g*y
27 楼
Great, this is the correct and best solution.
using
usin
ca
point
curren
r
initial
【在 Z*****Z 的大作中提到】
: The idea is to reconstruct the original tree while walking through it, using
: the given sequences. We use pre-order sequence to traverse down, while usin
: g post-order sequence to back out.
: The reconstructed tree will be a general tree, meaning each internal node ca
: n have arbitrary number of children. Also each node will have a parent point
: er.
: We need three pointers: treePtr, prePtr and postPtr that point to the curren
: t tree node, pre-order sequence and post-order sequence, respectively. The r
: oot is the first node of pre-order sequence, clearly. treePtr can be initial
: ized to point to root.
using
usin
ca
point
curren
r
initial
【在 Z*****Z 的大作中提到】
: The idea is to reconstruct the original tree while walking through it, using
: the given sequences. We use pre-order sequence to traverse down, while usin
: g post-order sequence to back out.
: The reconstructed tree will be a general tree, meaning each internal node ca
: n have arbitrary number of children. Also each node will have a parent point
: er.
: We need three pointers: treePtr, prePtr and postPtr that point to the curren
: t tree node, pre-order sequence and post-order sequence, respectively. The r
: oot is the first node of pre-order sequence, clearly. treePtr can be initial
: ized to point to root.
Z*Z
28 楼
thank you for providing this interesting problem!
【在 g*******y 的大作中提到】
: Great, this is the correct and best solution.
:
: using
: usin
: ca
: point
: curren
: r
: initial
【在 g*******y 的大作中提到】
: Great, this is the correct and best solution.
:
: using
: usin
: ca
: point
: curren
: r
: initial
H*r
29 楼
不紧这个思路太清晰了，parent pointer应用的实在巧妙啊！
using
usin
ca
point
curren
r
initial
【在 Z*****Z 的大作中提到】
: The idea is to reconstruct the original tree while walking through it, using
: the given sequences. We use pre-order sequence to traverse down, while usin
: g post-order sequence to back out.
: The reconstructed tree will be a general tree, meaning each internal node ca
: n have arbitrary number of children. Also each node will have a parent point
: er.
: We need three pointers: treePtr, prePtr and postPtr that point to the curren
: t tree node, pre-order sequence and post-order sequence, respectively. The r
: oot is the first node of pre-order sequence, clearly. treePtr can be initial
: ized to point to root.
using
usin
ca
point
curren
r
initial
【在 Z*****Z 的大作中提到】
: The idea is to reconstruct the original tree while walking through it, using
: the given sequences. We use pre-order sequence to traverse down, while usin
: g post-order sequence to back out.
: The reconstructed tree will be a general tree, meaning each internal node ca
: n have arbitrary number of children. Also each node will have a parent point
: er.
: We need three pointers: treePtr, prePtr and postPtr that point to the curren
: t tree node, pre-order sequence and post-order sequence, respectively. The r
: oot is the first node of pre-order sequence, clearly. treePtr can be initial
: ized to point to root.
j*2
30 楼
Excellent! Thanks a lot!
Get
GetAllInOrdersFromPreOrder.
【在 z*********g 的大作中提到】
: 我正好做过一个讲解视频 http://www.youtube.com/watch?v=rvMOG_yKBA0
: java的代码在这里：https://dl.dropbox.com/u/14935294/ProgrammingVideos/44-Get
: _All_Possible_In_Orders_From_Pre_Order_Traversal/GetAllInOrdersFromPreOrder.
: java
Get
GetAllInOrdersFromPreOrder.
【在 z*********g 的大作中提到】
: 我正好做过一个讲解视频 http://www.youtube.com/watch?v=rvMOG_yKBA0
: java的代码在这里：https://dl.dropbox.com/u/14935294/ProgrammingVideos/44-Get
: _All_Possible_In_Orders_From_Pre_Order_Traversal/GetAllInOrdersFromPreOrder.
: java
j*2
31 楼
do{
// traverse up the tree using post-order sequence
treePtr = treePtr.parent;
postPtr = next(postPtr); //what is the value of postPtr here? How can
this make us go back to the root?
} while(postPtr is not leaf);
Also, is it true that (preorder, postorder) can uniquely determine a general
tree?
Many thanks!
using
usin
ca
point
curren
r
initial
【在 Z*****Z 的大作中提到】
: The idea is to reconstruct the original tree while walking through it, using
: the given sequences. We use pre-order sequence to traverse down, while usin
: g post-order sequence to back out.
: The reconstructed tree will be a general tree, meaning each internal node ca
: n have arbitrary number of children. Also each node will have a parent point
: er.
: We need three pointers: treePtr, prePtr and postPtr that point to the curren
: t tree node, pre-order sequence and post-order sequence, respectively. The r
: oot is the first node of pre-order sequence, clearly. treePtr can be initial
: ized to point to root.
// traverse up the tree using post-order sequence
treePtr = treePtr.parent;
postPtr = next(postPtr); //what is the value of postPtr here? How can
this make us go back to the root?
} while(postPtr is not leaf);
Also, is it true that (preorder, postorder) can uniquely determine a general
tree?
Many thanks!
using
usin
ca
point
curren
r
initial
【在 Z*****Z 的大作中提到】
: The idea is to reconstruct the original tree while walking through it, using
: the given sequences. We use pre-order sequence to traverse down, while usin
: g post-order sequence to back out.
: The reconstructed tree will be a general tree, meaning each internal node ca
: n have arbitrary number of children. Also each node will have a parent point
: er.
: We need three pointers: treePtr, prePtr and postPtr that point to the curren
: t tree node, pre-order sequence and post-order sequence, respectively. The r
: oot is the first node of pre-order sequence, clearly. treePtr can be initial
: ized to point to root.
l*i
32 楼
Do you really need two sequences, seems one of them suffices since you have
is_leaf information. Let's look at preorder sequence:
let the sequence be node[0] to node[n-1]
you know node[n-1] has to be a leaf, actually the last leaf if you order the
leaves left to right.
Now start from pos=n-1, pos-- until you hit a node[i] which is_leaft ==
false. This node has to be the parent of node[i+1..n-1]. So you construct
such a tree node with the children i+1 to n-1. Now you can treat the tree
node as a leaf, that is, you collapse the subtree rooted at node[i] into a
single node. Then you can repeat the same step until the full tree is
constructed.
any problem with the idea?
leaf
【在 g*******y 的大作中提到】
: This one is too easy, not interesting.
: Try this one, which is more interesting (and difficult):
: Given pre-order and post-order sequences of {string node_value, bool is_leaf
: } of a GENERAL tree, reconstruct the tree, HOWEVER, "node_value" CANNOT be
: used to identify a node (i.e., there could be duplicate node values).
is_leaf information. Let's look at preorder sequence:
let the sequence be node[0] to node[n-1]
you know node[n-1] has to be a leaf, actually the last leaf if you order the
leaves left to right.
Now start from pos=n-1, pos-- until you hit a node[i] which is_leaft ==
false. This node has to be the parent of node[i+1..n-1]. So you construct
such a tree node with the children i+1 to n-1. Now you can treat the tree
node as a leaf, that is, you collapse the subtree rooted at node[i] into a
single node. Then you can repeat the same step until the full tree is
constructed.
any problem with the idea?
leaf
【在 g*******y 的大作中提到】
: This one is too easy, not interesting.
: Try this one, which is more interesting (and difficult):
: Given pre-order and post-order sequences of {string node_value, bool is_leaf
: } of a GENERAL tree, reconstruct the tree, HOWEVER, "node_value" CANNOT be
: used to identify a node (i.e., there could be duplicate node values).
T*r
33 楼
what's ur result for following pre-order traversal sequence?
(7 F) (3 F) (5 T) (6 T) (4 T)
T/F means a node is/is not a leaf.
have
the
【在 l***i 的大作中提到】
: Do you really need two sequences, seems one of them suffices since you have
: is_leaf information. Let's look at preorder sequence:
: let the sequence be node[0] to node[n-1]
: you know node[n-1] has to be a leaf, actually the last leaf if you order the
: leaves left to right.
: Now start from pos=n-1, pos-- until you hit a node[i] which is_leaft ==
: false. This node has to be the parent of node[i+1..n-1]. So you construct
: such a tree node with the children i+1 to n-1. Now you can treat the tree
: node as a leaf, that is, you collapse the subtree rooted at node[i] into a
: single node. Then you can repeat the same step until the full tree is
(7 F) (3 F) (5 T) (6 T) (4 T)
T/F means a node is/is not a leaf.
have
the
【在 l***i 的大作中提到】
: Do you really need two sequences, seems one of them suffices since you have
: is_leaf information. Let's look at preorder sequence:
: let the sequence be node[0] to node[n-1]
: you know node[n-1] has to be a leaf, actually the last leaf if you order the
: leaves left to right.
: Now start from pos=n-1, pos-- until you hit a node[i] which is_leaft ==
: false. This node has to be the parent of node[i+1..n-1]. So you construct
: such a tree node with the children i+1 to n-1. Now you can treat the tree
: node as a leaf, that is, you collapse the subtree rooted at node[i] into a
: single node. Then you can repeat the same step until the full tree is
l*i
34 楼
7
|
3
| \ \
| | |
5 6 4
I found the mistake, there is another tree
7
| \
3 4
|\
5 6
|
3
| \ \
| | |
5 6 4
I found the mistake, there is another tree
7
| \
3 4
|\
5 6
T*r
35 楼
So you mean (7 (3 5 6 4)). What abt (7 (3 5 6) 4) or (7 (3 5) 6 4)?
【在 l***i 的大作中提到】
: 7
: |
: 3
: | \ \
: | | |
: 5 6 4
: I found the mistake, there is another tree
: 7
: | \
: 3 4
【在 l***i 的大作中提到】
: 7
: |
: 3
: | \ \
: | | |
: 5 6 4
: I found the mistake, there is another tree
: 7
: | \
: 3 4
i*e
36 楼
Mark
pr
★ 发自iPhone App: ChineseWeb 7.3
【在 Z*****Z 的大作中提到】
: 膜拜啊，好久不见这位神牛了，要往FB跳马？：）
: 我来抛砖引玉一下吧。我认为从先序、后序重构树，和只从先序重构树，的算法差不多
: 。
: 假设输入preList[1...N]和postList[1...N]分别代表先序和后序遍历的结果。
: 可以把先序遍历的第一个节点preList[1]当做根，剩下的的节点分成连续的两部分，pr
: eList[2,i], preList[i+1,N]（i = 1...N)，然后分别重构左、右子树。最后再把左右
: 子树交叉合并起来。
: 以第一次划分为例，对于i从1到N时的两个子问题分别为：
: preList[2...i], postList[1,i-1]
: preList[i+1...N], postList[i,N-1]
pr
★ 发自iPhone App: ChineseWeb 7.3
【在 Z*****Z 的大作中提到】
: 膜拜啊，好久不见这位神牛了，要往FB跳马？：）
: 我来抛砖引玉一下吧。我认为从先序、后序重构树，和只从先序重构树，的算法差不多
: 。
: 假设输入preList[1...N]和postList[1...N]分别代表先序和后序遍历的结果。
: 可以把先序遍历的第一个节点preList[1]当做根，剩下的的节点分成连续的两部分，pr
: eList[2,i], preList[i+1,N]（i = 1...N)，然后分别重构左、右子树。最后再把左右
: 子树交叉合并起来。
: 以第一次划分为例，对于i从1到N时的两个子问题分别为：
: preList[2...i], postList[1,i-1]
: preList[i+1...N], postList[i,N-1]
相关阅读
Re: 北航为何火？去航天单位也挣不了多少 (转载)女发考题吃了嫩草？ (转载)每天乐一乐，帮同事的妻子怀孕 Zz中国黑客攻韩军网，没瘫痪已经很给面子了印度为恒河授予人权 任命2名高官为其监护人 (转载)朋友圈保持沉默的重要性 (转载)单身久了被撩一下都觉得受宠若惊 zz德州提案禁止打飞机，违者将罚100美金非笑话信息，用wells fargo cc手机账单【Dreamer出品】中国伊朗首发预测（原创）找一部小电影讲因为一辆车时空交错的 (转载)《我不是潘金莲》被农妇潘金莲告了 冯小刚、范冰冰等不同意庭(转载)十条笑话：在女同事家酒足饭饱之后，说了几次要告辞了 zzRe: 泡软一路小跑刚去了白宫 (转载)看了乒乓球削球手的视频, 结果下面的第一条评论亮了如果亚当和夏娃是中国人，things are tastier《科学》重磅：确认！66%的癌症发生是因为这是什么足协：到2020年男足世界排名前70位 女足前10位十条笑话：公司组织体检，做胸透 zz