【每日刷题】从前序与中序遍历序列构造二叉树

题目地址

https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

题目描述：从前序与中序遍历序列构造二叉树

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

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

例如：

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

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

解答

序遍历的顺序是 root -> left -> right，这就能方便的从根开始构造一棵树。

首先，preorder 中的第一个元素一定是树的根，这个根又将 inorder 序列分成了左右两棵子树。现在我们只需要将先序遍历的数组中删除根元素，然后重复上面的过程处理左右两棵子树。

代码：

/**
 * 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:
    int findPos( int target, vector<int>& inorder, int start, int end){
        for( int i = start; i < end; i++)
            if( inorder[i] == target)
                return i;
        return -1;
    }
    TreeNode* build( vector<int>& preorder, int preBegin, vector<int>& inorder, int start, int end){
        if( start == end)   //边界条件
            return NULL;
        
        TreeNode* now = new TreeNode( preorder[preBegin]);
        int pos = findPos( preorder[preBegin], inorder, start, end);
        
        if( pos == -1)
            return now;
        
        now->left  = build( preorder, preBegin + 1, inorder, start, pos);
        now->right = build( preorder, preBegin + pos - start + 1, inorder, pos + 1, end);
        
        return now;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if( preorder.size() == 0)   return NULL;
        return build( preorder, 0, inorder, 0, inorder.size());
    }
};