LeetCode 106. 从中序与后序遍历序列构造二叉树
原题链接
中等
作者:
我要出去乱说
,
2021-07-24 13:21:32
,
所有人可见
,
阅读 197
class Solution {
public:
unordered_map<int, int> pos;
TreeNode* dfs(vector<int>& in, int il, int ir, vector<int>& post, int pl, int pr)
{
if (pl > pr) return nullptr;//pl == pr时表示叶子节点,pl > pr表示空节点
//k为当前根节点的左子树长度,即中序遍历中根节点位置减去第一个节点的位置
int k = pos[post[pr]] - il;
TreeNode* root = new TreeNode(post[pr]);
root->left = dfs(in, il, il + k - 1, post, pl, pl + k - 1);
root->right = dfs(in, il + k + 1, ir, post, pl + k, pr - 1);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int n = inorder.size();
if (n == 0) return nullptr;
//哈希映射,为了找到前序遍历第一个元素(根节点)在中序遍历中的位置,以此来判断左右子树的长度
for (int i = 0; i < n; ++ i) pos[inorder[i]] = i;
return dfs(inorder, 0, n - 1, postorder, 0, n - 1);
}
};