用前序和中序遍歷構(gòu)建二叉樹(shù)

/**

* Definition for binary tree

* struct TreeNode {

*? ? int val;

*? ? TreeNode *left;

*? ? TreeNode *right;

*? ? TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

*/

class Solution {

public:

? ? TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {

? ? ? ? TreeNode* tree;

? ? ? ? tree = GetSubTree(pre,vin,0,pre.size()-1,0,vin.size()-1);

? ? ? ? return tree;

? ? }

? ? TreeNode* GetSubTree(vector<int>&pre, vector<int>&vin, int pre_l,int pre_r,int in_l,int in_r)

? ? {

? ? ? ? if(pre_l>pre_r||in_l>in_r)

? ? ? ? {?

? ? ? ? ? ? return NULL;

? ? ? ? }

? ? ? ? //中序遍歷中的父節(jié)

? ? ? ? int mid = in_l;

? ? ? ? while(mid<=in_r&&vin[mid]!=pre[pre_l]){mid++;}

? ? ? ? //得到左子子樹(shù)的長(zhǎng)度

? ? ? ? int left_num = mid-in_l;

? ? ? ? TreeNode* T = new TreeNode(pre[pre_l]);

? ? ? ? T->left = GetSubTree(pre,vin,pre_l+1, left_num+pre_l,in_l,mid-1);

? ? ? ? T->right = GetSubTree(pre,vin,left_num+pre_l+1,pre_r,mid+1,in_r);

? ? ? ? return T;

? ? }

};