[leetcode] 105. Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

解题思路：
本题要求我们在给定二叉树的前序遍历数组和中序遍历数组的情况下，构造二叉树。基本思路如下：

• 前序遍历数组的第一个数preorder[0]就是二叉树的根节点
• 遍历中序数组，找到根节点，假设为inorder[i]
• 假定数组的长度为n, 则inorder[0]...inorder[i-1]构成左子树，inorder[i+1]...inorder[n]构成右子树。
• 重复以上过程，即可构造二叉树。

具体代码如下：

class Solution {
public:
    TreeNode* buildTreeHelper(int preStart, int inStart, int inEnd, vector<int>& preorder, vector<int>& inorder)
    {
        if(preStart > preorder.size() -1 || inStart > inEnd) //右子树为空的情况下，preStart == preorder.size() -1
            return NULL;
            
        int index = 0;
        TreeNode *root = new TreeNode(preorder[preStart]);
        for(int i = 0; i< inorder.size();++i)
        {
            if(inorder[i] == preorder[preStart])
                index = i;
        }
        
        root->left = buildTreeHelper(preStart + 1, inStart, index - 1, preorder,inorder);
        root->right = buildTreeHelper(preStart + index - inStart + 1, index + 1, inEnd, preorder,inorder); // 构造右子树的时候，preStart,index,inStart都是数组中的绝对位置，preStart应该加上偏移量，因此为preStart + index - inStart + 1， preStart和inStart不一定相等
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return buildTreeHelper(0,0,inorder.size() -1,preorder,inorder);
    }
};