Leedcode编程题-剑指 Offer 07 - 重建二叉树----C++实现

本文主要是介绍Leedcode编程题-剑指 Offer 07 - 重建二叉树----C++实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目的：

旨在记录在Leedcode网上刷题的过程，记录心得。

题目：

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

3
/ \
9 20
/ \
15 7

限制：

0 <= 节点个数 <= 5000

思路：

前序遍历：根左右

中序遍历：左根右

由前序遍历的结果中的元素将中序遍历结果中的元素分为2部分（左右子树2部分）；

再分别递归处理左右子树的重建：

如果只有前序序列，我们除了第一个位置知道肯定是根节点之外，其他都不能确定；

如果只有中序序列，我们只知道第一个值是整个树最左边的节点，最后一个值是整个树最右边的节点；

对照起来看，通过根节点的值，就可以将中序序列一分为二，前面是根节点左子树，后面是根节点右子树；

再通过左子树序列的长度，又可以从前序序列中找到对应长度的前序序列；

有了左右子树对应的前序序列和中序序列，按照同样的方式，就可以递归建树。

代码：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*//*前序遍历：根左右中序遍历：左根右由前序遍历的结果中的元素将中序遍历结果中的元素分为2部分（左右子树2部分）；再分别递归处理左右子树的重建：如果只有前序序列，我们除了第一个位置知道肯定是根节点之外，其他都不能确定；如果只有中序序列，我们只知道第一个值是整个树最左边的节点，最后一个值是整个树最右边的节点；对照起来看，通过根节点的值，就可以将中序序列一分为二，前面是根节点左子树，后面是根节点右子树；再通过左子树序列的长度，又可以从前序序列中找到对应长度的前序序列；有了左右子树对应的前序序列和中序序列，按照同样的方式，就可以递归建树。*/
class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.size()!=inorder.size()||inorder.size()==0) return NULL;return rebuildTree(preorder,inorder,0,0,inorder.size());}TreeNode* rebuildTree(vector<int>& preorder, vector<int>& inorder,int preId,int inLeftStart,int inRightEnd){if(inLeftStart==inRightEnd) return NULL;int val = preorder[preId];int inIdx = inLeftStart;while(inorder[inIdx]!=val)  inIdx++;int inLeftEnd = inIdx;int inRightStart = inIdx + 1;TreeNode *root = new TreeNode(val);root->left = rebuildTree(preorder,inorder,preId+1,inLeftStart,inLeftEnd);root->right = rebuildTree(preorder,inorder,preId+1+(inLeftEnd-inLeftStart),inRightStart,inRightEnd);return root;}
};