从中序和层序遍历构造二叉树

Question

首先，我想声明这不是家庭作业。我正在准备面试并遇到这个问题。我想我们可以通过中序和级序遍历的定义。:-)。

例如：

      50
   /      \
 10        60
/  \       /  \
5   20    55    70
        /     /  \
      51     65    80

上述树的中序和层序遍历为：

5、10、20、50、51、55、60、65、70、80

50, 10, 60, 5, 20, 55, 70, 51, 65, 80

我的点子：

(1) 遍历层序数组，找出出现在有序数组中的第一个元素。我们称这个元素为当前根。

(2) 在有序数组中找到当前根的索引。中序数组由索引分隔。中序数组的左边是当前根的左子树，中序数组的右边是当前根的右子树。

(3) 将有序数组更新为左边，然后转到步骤1。

(4) 将中序数组更新为其右侧，然后转到步骤2。

以上面的树为例。

(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 ...

谁能帮我验证我的解决方案？如果再给一个，真的很感激。

Answer 1

其实思路很简单，只要保证遍历顺序正确与否就可以了。比如你要做中序遍历，你可以简单的这样想：从左到右，从下到上。

1. 遍历到同一节点的左下（5），然后遍历到右下（20）。

2. 从底部 (10) 遍历到顶部 (50)。

3. 在左边做同样的事情。

对于杠杆顺序，你可以从上到下，从左到右，一步一步地遍历。