LeetCode OJ:Construct Binary Tree from Preorder and Inorder Traversal

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.

算法思想：

1、先序序列的第一个元素是该树的根；

2、中序序列该元素将该树分为左右两个子树，该元素位置设为i

3、中序序列的0到i-1元素为左子树，对应于先序序列的1到i元素，中序右子树i+1到in_end对应先序的i+1到pre_end元素

所以对于左子树和右子树也满足以上性质，递归即可

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void build(vector
  
    &preorder, vector
   
     &inorder, TreeNode * &root, int pre_start, int pre_end,int in_start, int in_end){ if(in_start>in_end)return; root = new TreeNode(preorder[pre_start]); int i; for(i = in_start; i<=in_end; i++) if(inorder[i]==preorder[pre_start]) break; int pre_mid = pre_start+i-in_start; build(preorder, inorder, root->left, pre_start+1, pre_mid, in_start, i-1); build(preorder, inorder, root->right, pre_mid+1, pre_end, i+1, in_end); } TreeNode *buildTree(vector
    
      &preorder, vector
     
       &inorder) { if(!inorder.size())return NULL; TreeNode *root = NULL; build(preorder, inorder, root, 0, preorder.size()-1, 0, inorder.size()-1); return root; } };