[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal - c++编程基础

Note:

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

问题描述：给定一个二叉树的前序遍历和中序遍历序列，构建这个二叉树。

二叉树的问题通常可以采用递归的方式。

知道一个子树的前序，那么就可以知道该子树的根，然后在中序中找到这个根，就可以知道左右子树的前序和中序遍历序列。

class Solution {  
public:  
    typedef vector::iterator bt_iter;  
  
    TreeNode *build(bt_iter pre_beg, bt_iter pre_end, bt_iter in_beg, bt_iter in_end)  
    {  
        if(pre_beg == pre_end)  
            return NULL;  
  
        int root_val = *pre_beg;  
        bt_iter rt_it = find(in_beg, in_end, root_val);  
        bt_iter left_end = pre_beg + (rt_it - in_beg);  
  
        TreeNode *child_root = new TreeNode(root_val);  
        child_root->




left = build(pre_beg + 1, left_end + 1, in_beg, rt_it - 1);  
        child_root->right = build(left_end + 1, pre_end, rt_it + 1, in_end);  
  
        return child_root;  
    }  
  
    TreeNode *buildTree(vector &preorder, vector &inorder) {  
        // IMPORTANT: Please reset any member data you declared, as  
        // the same Solution instance will be reused for each test case.  
        return build(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());   
    }  
};