题意:输入一棵二叉树前序遍历和中序遍历的结果,请重建该二叉树。
算法:递归
思路:1)利用前序遍历找根节点,即前序遍历的第一个值就是根节点的值
2)利用中序遍历找左右子树,通过前序遍历的第一个值找到中序遍历该值的下标,其左边为左子树,右边为右子树
3)通过中序遍历划分出来的左右子树个数找前序遍历的左右子树,假设中序遍历的找到的左子树个数为l,则前序
遍历根节点后面l个数时左子树,其余后面的数为右子树
4)递归构造左右子树
时间复杂度:O(n)
unordered_map<int, int> hash;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
// 将中序遍历每个数对应的下标存入哈希表,方便从根节点的值找到中序下标
for(int i = 0;i < n;i ++) hash[inorder[i]] = i;
return dfs(preorder, inorder, 0, n - 1, 0, n - 1);
}
TreeNode* dfs(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir)
{
if(pl > pr) return NULL;
int val = preorder[pl];
int k = hash[val];
int len = k - il;
auto root = new TreeNode(val);
root -> left = dfs(preorder, inorder, pl + 1, pl + len, il, k - 1);
root -> right = dfs(preorder, inorder, pl + len + 1, pr, k + 1, ir);
return root;
}
网友评论