由前序遍历和中序遍历树构造二叉树

  1
 / 
2   3
    
  4   5

 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
 

class Solution {
    
     *@param preorder : A list of integers that preorder traversal of a tree
     *@param inorder : A list of integers that inorder traversal of a tree
     *@return : Root of a tree
     */
public:
    TreeNode *(vector<int> &preorder, vector<int> &inorder) {
        int len_pre = preorder.size(), len_in = inorder.size();
        if (!len_in || !len_pre) return NULL;
        TreeNode *root = new TreeNode(preorder[0]);
        int in = 0;  // in: 中序遍历根节点所在位置
        while (preorder[0] != inorder[in]) in++;  // 在中序遍历找到根节点位置
        preorder.erase(preorder.begin()); // 去除preorder的第一个元素
        vector<int>::iterator it_in = inorder.begin();
        vector<int> inorder_left, inorder_right;
        if (in != 0)  // 有左子树
        {
            inorder_left = vector<int>(it_in, it_in + in);  // 左侧子树的中序遍历
        }
        if (in != len_in -1)  // 有右子树
        {
            inorder_right = vector<int>(it_in + in + 1, inorder.end());  // 右侧子树的中序遍历
        }
        root->left = buildTree(preorder, inorder_left);  // 构造左子树
        root->right = buildTree(preorder, inorder_right);  // 构造右子树
        return root;
    }
};