105. 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

1
2
3
4
前序遍历 
    preorder = [3,9,20,15,7]
中序遍历 
    inorder = [9,3,15,20,7]

返回如下的二叉树：

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

Solution1（递归版）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int s = 0;
        return buildNode(preorder, s, inorder, 0, inorder.size()-1);
    }
    
    TreeNode* buildNode(vector<int>& preorder, int &preindex, vector<int>& inorder, int start, int end){
        if(start <= end){
            int inIndex = INT_MAX;
            for(int i = start; i <= end; i++){
                if(inorder[i] == preorder[preindex]) {
                    inIndex = i;
                    break;
                }
            }
            if(inIndex < start || inIndex > end) return NULL;
            TreeNode* node = new TreeNode(preorder[preindex++]);
            node->left = buildNode(preorder, preindex, inorder, start, inIndex-1);
            node->right = buildNode(preorder,preindex , inorder, inIndex+1, end);
            return node;
        }
        return NULL;
        
    }
};

思路:

在前序遍历中，根结点是第一个元素。在中序遍历中，根节点之前的元素都在根结点的左子树上。根节点之后的元素都在根节点的右子树上。
对于其他的结点，与根节点构建的方式一样。所以可以使用递归。

所以重点就是找到根节点在中序遍历中的位置。

每次找到前序遍历中的一个结点，在中序遍历中找到该结点的位置，建立该结点。然后给该结点之下的结点（子树）划分区域。继续递归下去，直到区域缩小为0为止。

Solution2（迭代版）: