题解 | #重建二叉树#

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
   	vector<int>pv, iv;//前序，中序

	//根据前序与中序返回一棵树，四个参数依次是前序开始，前序结束，中序开始，中序结束
	TreeNode* helper(int pre_beg, int pre_end, int in_beg,int in_end) {

		if (pre_beg > pre_end || in_beg > in_end)return NULL;

		TreeNode *root = new TreeNode(pv[pre_beg]);
		//找到根节点在中序iv中的位置
		int pos;
		for(int i=in_beg;i<=in_end;i++)
			if (iv[i] == pv[pre_beg]) { pos = i; break; }

		int b;
		//左子树
		b = pre_beg + pos - in_beg;//左子树在前序序列中最后一个节点的位置
		root->left = helper(pre_beg + 1, b, in_beg, pos - 1);
		//右子树
		root->right = helper(b + 1, pre_end, pos + 1, in_end);

		return root;
	}
	TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
		if (pre.size() == 0)return NULL;
		pv = pre; iv = vin;
		return helper(0, pre.size()-1, 0, vin.size()-1);
	}

};