construct a binary tree from in-order and level-order trav# JobHunting - 待字闺中
x*0
1 楼
I guess we can pass the definition of in-order and level-order traversal. :-
).
For example:
50
/ \
10 60
/ \ / \
5 20 55 70
/ / \
51 65 80
The in-order and level-order traversal of the above tree are:
5, 10, 20, 50, 51, 55, 60, 65, 70, 80
50, 10, 60, 5, 20, 55, 70, 51, 65, 80
My idea:
(1) traversal the level-order array to find out the first element which
appears in the in-order array. We call this element as current root.
(2) find the index of current root in the in-order array. The in-order array
is separated by the index. The left side of the in-order array is the left
sub-tree of the current root and the right side of the in-order array is the
right sub-tree of the current root.
(3) update the in-order array as its left side and then go to step 1.
(4) update the in-order array as its right side and then go to step 2.
Take the above tree as an example.
(1) 5 is the first element appears in the in-order array.
(2) [50 ...60] is the left sub-tree of 5 and [20 ... 80] is the right sub-
tree of 5.
(3) update the in-order array as [50 ... 60]
(1) 10 is the first element appears in [50 10 60].
(2) [50] is the left sub-tree of 10 and [60] is the right sub-tree of 10.
(3) update ...
Can anyone help me verify it?
And really appreciate giving another solution~
Thanks,
Zhong
).
For example:
50
/ \
10 60
/ \ / \
5 20 55 70
/ / \
51 65 80
The in-order and level-order traversal of the above tree are:
5, 10, 20, 50, 51, 55, 60, 65, 70, 80
50, 10, 60, 5, 20, 55, 70, 51, 65, 80
My idea:
(1) traversal the level-order array to find out the first element which
appears in the in-order array. We call this element as current root.
(2) find the index of current root in the in-order array. The in-order array
is separated by the index. The left side of the in-order array is the left
sub-tree of the current root and the right side of the in-order array is the
right sub-tree of the current root.
(3) update the in-order array as its left side and then go to step 1.
(4) update the in-order array as its right side and then go to step 2.
Take the above tree as an example.
(1) 5 is the first element appears in the in-order array.
(2) [50 ...60] is the left sub-tree of 5 and [20 ... 80] is the right sub-
tree of 5.
(3) update the in-order array as [50 ... 60]
(1) 10 is the first element appears in [50 10 60].
(2) [50] is the left sub-tree of 10 and [60] is the right sub-tree of 10.
(3) update ...
Can anyone help me verify it?
And really appreciate giving another solution~
Thanks,
Zhong