• 如果您觉得本站非常有看点，那么赶紧使用Ctrl+D 收藏吧

# 重建二叉树（剑指 Offer）

2周前 (11-21) 9次浏览

``````前序遍历 preorder = [3,9,20,15,7]

``````    3
/
9  20
/
15   7``````

`0 <= 节点个数 <= 5000`

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/

class Solution {
public:
TreeNode* buildTreeCode(vector<int>&preorder, int prestart, int preend, vector<int>& inorder, int inostart, int inoend)
{
if (prestart>preend || inostart > inoend)
{
return nullptr;
}
TreeNode *root = new TreeNode(preorder[prestart]);
for (auto i = inostart; i <= inoend; i++)
{
if (preorder[prestart] == inorder[i])
{
root->left = buildTreeCode(
preorder, prestart + 1, i - inostart + prestart,
inorder, inostart, i - 1);
//在前序排列中root就是prestart，所以prestart不在区间内
root->right = buildTreeCode(
preorder, i - inostart + prestart + 1, preend,
inorder, i + 1, inoend);
//在中序排列中第I个就是root所以在区间内不包括i
break;
}
}
return root;
}
TreeNode* buildTree(vector<int> &preorder, vector<int>&inorder) {
if (preorder.empty() || inorder.empty())
{
return nullptr;
}
return  buildTreeCode(
preorder, 0, preorder.size() - 1,
inorder, 0, inorder.size() - 1);
}
};
``````

``````class Solution {
public:
TreeNode* buildTreeCode(
vector<int>::iterator preBegin,
vector<int>::iterator preEnd,
vector<int>::iterator inBegin,
vector<int>::iterator inEnd)
{
if (inBegin == inEnd)
{
return nullptr;
}
TreeNode*cur = new TreeNode(*preBegin);
auto root = find(inBegin, inEnd, *preBegin);
cur->left = buildTreeCode(
preBegin + 1, preBegin + 1 + (root - inBegin),
inBegin, root);
//区间是左闭右开
cur->right = buildTreeCode(
preBegin + 1 + (root - inBegin), preEnd,
root + 1, inEnd);
return cur;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {

if (preorder.empty() || inorder.empty())
{
return nullptr;
}
return buildTreeCode(preorder.begin(), preorder.end(),
inorder.begin(), inorder.end());
}
};``````