I**A
发帖数: 2345 | 1 Given the pre-order and in-order traversing result of a binary tree, write a
function to rebuild the tree
ideas? |
d****2
发帖数: 6250 | 2 find root from pre-order tree, use that to split left-tree, right-tree from
in-order list, recursively go down. |
I**A
发帖数: 2345 | 3 don't understand how to do this recursively.. //羞愧
from
【在 d****2 的大作中提到】
: find root from pre-order tree, use that to split left-tree, right-tree from
: in-order list, recursively go down.
|
d****2
发帖数: 6250 | 4 preorder: 1 2 3 4 5
inorder: 3 2 4 1 5
root 1
left subtree preorder 2 3 4
left subtree inorder 3 2 4
right subtree preorder 5
right subtree inorder 5
recursively work on left subtree and right subtree with the known
preorder and inorder lists. |
I**A
发帖数: 2345 | 5 thanks a lot..
i can manually construct it, but 写不出来 this recursive code. :(
能否写个code看看？
【在 d****2 的大作中提到】
: preorder: 1 2 3 4 5
: inorder: 3 2 4 1 5
: root 1
: left subtree preorder 2 3 4
: left subtree inorder 3 2 4
: right subtree preorder 5
: right subtree inorder 5
: recursively work on left subtree and right subtree with the known
: preorder and inorder lists.
|
d****2
发帖数: 6250 | 6 struct tree_node {
int x;
tree_node *left;
tree_node *right;
};
tree_node *build_tree(const std::vector &preorder, int start1, int end1
, const std::vector &inorder, int start2, int end2) {
if (start1 > end1)
return NULL;
if (start1 == end1) {
tree_node *tn = new tree_node;
tn->x = preorder[start1];
tn->left = NULL;
tn->right = NULL;
return tn;
}
int pos;
for (pos = start2; pos <= end2; pos++)
if (inorder[pos] == preorder[start1])
|
I**A
发帖数: 2345 | 7 thanks so much first~
等我仔细看
end1
【在 d****2 的大作中提到】
: struct tree_node {
: int x;
: tree_node *left;
: tree_node *right;
: };
: tree_node *build_tree(const std::vector &preorder, int start1, int end1
: , const std::vector &inorder, int start2, int end2) {
: if (start1 > end1)
: return NULL;
: if (start1 == end1) {
|
j**l
发帖数: 2911 | 8 写个简洁的从前序和中序序列重建二叉树的代码，以飨版友。
TreeNode* rebuild(char *pstr, char *istr, int n)
{
if (n <= 0)
return NULL;
TreeNode* root = new TreeNode;
root->data = *pstr;
char* iter;
for (iter = istr; iter < istr + n; iter++)
{
if (*iter == *pstr)
break;
}
int k = iter - istr;
root->left = rebuild(pstr + 1, istr, k);
root->right = rebuild(pstr + k + 1, iter + 1, n - k - 1);
return root;
} |
j**l
发帖数: 2911 | 9 这个是一年前Amazon问我的电面题。
a
【在 I**A 的大作中提到】
: Given the pre-order and in-order traversing result of a binary tree, write a
: function to rebuild the tree
: ideas?
|
l*******g
发帖数: 4894 | 10 这个也太常规了吧。choose root from pre-order, all the left nodes are listed
on the left in the in-order traverse, vice versa.
a
【在 I**A 的大作中提到】
: Given the pre-order and in-order traversing result of a binary tree, write a
: function to rebuild the tree
: ideas?
|
|
|
d**e
发帖数: 6098 | 11 果然简洁。
发觉自己真的弱，写了一个多小时才写出无bug能正确运行的code....要多做题才行。
【在 j**l 的大作中提到】
: 写个简洁的从前序和中序序列重建二叉树的代码，以飨版友。
: TreeNode* rebuild(char *pstr, char *istr, int n)
: {
: if (n <= 0)
: return NULL;
: TreeNode* root = new TreeNode;
: root->data = *pstr;
: char* iter;
: for (iter = istr; iter < istr + n; iter++)
: {
|
I**A
发帖数: 2345 | 12 这个和地主那个，各有利弊，地主那个很好理解。。
这个有没有bug？我写了个java version，对某些树，不work, 帮着看看，哪儿的问题？
public static Node buildTree(int[] preorder, int start1, int[] inorder,
int start2, int len){
if(len<=0)
return null;
Node node = new Node(preorder[start1]);
int k;
for(k=start2; k
if(inorder[k] == preorder[start1])
break;
if(k==start2+len)
return null;
node
【在 j**l 的大作中提到】
: 写个简洁的从前序和中序序列重建二叉树的代码，以飨版友。
: TreeNode* rebuild(char *pstr, char *istr, int n)
: {
: if (n <= 0)
: return NULL;
: TreeNode* root = new TreeNode;
: root->data = *pstr;
: char* iter;
: for (iter = istr; iter < istr + n; iter++)
: {
|
d****2
发帖数: 6250 | 13
题？
,
len-k-1
【在 I**A 的大作中提到】
: 这个和地主那个，各有利弊，地主那个很好理解。。
: 这个有没有bug？我写了个java version，对某些树，不work, 帮着看看，哪儿的问题？
: public static Node buildTree(int[] preorder, int start1, int[] inorder,
: int start2, int len){
: if(len<=0)
: return null;
:
: Node node = new Node(preorder[start1]);
:
: int k;
|
I**A
发帖数: 2345 | 14 huh? where?
【在 d****2 的大作中提到】
:
: 题？
: ,
: len-k-1
|
d****2
发帖数: 6250 | 15
node.right = buildTree(preorder, start1+1+(k-start2), inorder, k+1,
len-k-1);
【在 I**A 的大作中提到】
: huh? where?
|
I**A
发帖数: 2345 | 16 没明白，有什么问题？
right tree should have len-k-1 nodes bah, no?
【在 d****2 的大作中提到】
:
: node.right = buildTree(preorder, start1+1+(k-start2), inorder, k+1,
: len-k-1);
|
d****2
发帖数: 6250 | 17 left: k-start2
right: len-k-1
sum of above two is not len-1. |
I**A
发帖数: 2345 | 18 多谢多谢！
我太笨了～～～～～
【在 d****2 的大作中提到】
: left: k-start2
: right: len-k-1
: sum of above two is not len-1.
|
c*r
发帖数: 9 | 19 这个题如果有重复值是不是就不行了？
【在 j**l 的大作中提到】
: 写个简洁的从前序和中序序列重建二叉树的代码，以飨版友。
: TreeNode* rebuild(char *pstr, char *istr, int n)
: {
: if (n <= 0)
: return NULL;
: TreeNode* root = new TreeNode;
: root->data = *pstr;
: char* iter;
: for (iter = istr; iter < istr + n; iter++)
: {
|
I**A
发帖数: 2345 | 20 nod.
the values should be unique
【在 c*r 的大作中提到】
: 这个题如果有重复值是不是就不行了？
|
|
|
H****r
发帖数: 2801 | 21 The posts before are O(N lgN). There's a O(N) algorithm.
a
【在 I**A 的大作中提到】
: Given the pre-order and in-order traversing result of a binary tree, write a
: function to rebuild the tree
: ideas?
|
H****r
发帖数: 2801 | 22 Take a look at this paper:
http://user.it.uu.se/~arnea/ps/optcons.pdf
【在 H****r 的大作中提到】
: The posts before are O(N lgN). There's a O(N) algorithm.
:
: a
|
I**A
发帖数: 2345 | 23 要命了
怎么算法无止境啊？？？？
【在 H****r 的大作中提到】
: Take a look at this paper:
: http://user.it.uu.se/~arnea/ps/optcons.pdf
|
