LeetCode105 从前序遍历和中序遍历构造二叉树

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

递归，根据前序遍历当前有效区域第一个，即为当前根节点；找到中序遍历中它的位置，左侧为左节点，右侧为右节点。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
13         int len=preorder.size();
14         //preorder.size()!=inorder.size(), set global variable
15         return recursive_build(preorder,0,len-1,inorder,0,len-1);
16     }
17 
18     TreeNode* recursive_build(vector<int>& preorder, int startpre, int endpre, vector<int>& inorder, int startin, int endin){
19         if(startpre>endpre)
20             return nullptr;
21         if(startpre==endpre)
22             return new TreeNode(preorder[startpre]);
23         int rootval=preorder[startpre];
24         int posin=startin;
25         while(inorder[posin]!=rootval && posin<=endin)
26             ++posin;
27         //posin>endin, set g_variable
28         TreeNode* curNode=new TreeNode(rootval);
29         int leftlen=posin-startin;
30         curNode->left=recursive_build(preorder,startpre+1,startpre+leftlen,inorder,startin,posin-1);
31         curNode->right=recursive_build(preorder,startpre+leftlen+1,endpre,inorder,posin+1,endin);
32         return curNode; 
33     }
34 };