7. 重建二叉树
1. 描述
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
2 限制
- 0 <= 节点个数 <= 5000
3. 题解
n = i_preorder.size()
时间复杂度: O(n)
空间复杂度: O(n)
根据定义递归建树
class Solution
{
private:
TreeNode* buildTree(vector<int> &i_preorder, int preLeft, int preRight,
vector<int> &i_inorder, int inLeft, int inRight)
{
if(preLeft > preRight || inLeft > inRight) return nullptr;
auto root = new TreeNode(i_preorder[preLeft]);
if(preLeft == preRight)
{
return root;
}
else
{
int rootIndexAtInorder = find(i_inorder.begin(), i_inorder.end(), i_preorder[preLeft]) - i_inorder.begin();
int leftSubTreeNodeCount = rootIndexAtInorder - inLeft;
int rightSubTreeNodeCount = inRight - rootIndexAtInorder;
root->left = buildTree(i_preorder, preLeft + 1, preLeft + leftSubTreeNodeCount,
i_inorder, inLeft, rootIndexAtInorder - 1);
root->right = buildTree(i_preorder, preRight - rightSubTreeNodeCount + 1, preRight,
i_inorder, rootIndexAtInorder + 1, inRight);
return root;
}
}
public:
// TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
TreeNode* buildTree(vector<int> &i_preorder, vector<int> &i_inorder)
{
if(i_preorder.empty() || i_preorder.size() != i_inorder.size()) return nullptr;
return buildTree(i_preorder, 0, i_preorder.size() - 1, i_inorder, 0, i_inorder.size() - 1);
}
};