题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

本题采用递归思路求解

递归思路：如果遍历序列为空，返回空；在中序遍历中找到前序遍历的第一个元素（即根节点），找到根节点后记录根节点左子树的前序遍历和中序遍历，记录根节点右子树的中序遍历，把得到的相对应的前序遍历和中序遍历重复上面的过程即可。代码如下，仅供参考。

/**

 * 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) {

		if(pre.size()==0||vin.size()==0){          //递归跳出条件

			return NULL;

		}

		TreeNode *root = new TreeNode(pre[0]);

		int i;

		for(i=0;i<vin.size()&&vin[i]!=pre[0];i++); //找到根节点对应的元素值索引

		vector<int> pre_left,pre_right,vin_left,vin_right;

		int pre_i = 1;                             //标记pre容器的下表，根节点索引为0，所以从1开始，把pre容器分成两个容器

		for(int j=0;j<vin.size();j++){

			if(j<i){

				vin_left.push_back(vin[j]);

				pre_left.push_back(pre[pre_i]);

				pre_i++;

			}else if(j>i){

				vin_right.push_back(vin[j]);

				pre_right.push_back(pre[pre_i]);

				pre_i++;

			}

		}

		root->left = reConstructBinaryTree(pre_left,vin_left);

		root->right = reConstructBinaryTree(pre_right,vin_right);

		return root;

	}

};

巴特西

剑指offer--（根据前序遍历和中序遍历）重建二叉树

题目描述

最新文章

热门文章