从中序与后续遍历序列构造二叉树(详细注释)
备忘
思想
与上一题《从先序与中序遍历序列构造二叉树》思路一致,可参考此题题解:
https://www.acwing.com/solution/content/27602
先序 + 中序:[根节点 | 左子树 | 右子树] + [左子树 | 根节点 | 右子树] ->
后序 + 中序;[左子树 | 右子树 | 根节点] + [左子树 | 根节点 | 右子树];
只不过先序序列的根节点root在序列开头,左子树根节点索引等于root + 1,右子树根节点索引等于root + 1 + 左子树元素数量;
后序序列的根节点root在序列开头,右子树根节店索引等于root - 1,左子树根节点索引等于root - 1 - 右子树元素数量。
C++ 代码
class Solution {
public:
unordered_map<int, int> dict;//创建哈希表存储中序序列中元素对应的下标
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int len = inorder.size();
for(int i = 0; i < len; i ++ ){
dict[inorder[i]] = i;//存储
}
//后序序列的根节点一定从len - 1开始
return build(len - 1, 0, len - 1, postorder);
}
TreeNode* build(int root, int left, int right, vector<int>& postorder){
//root是后序序列中的索引,left、right是中序序列的索引
if(left > right) return NULL;//若left==right当前节点是叶子结点,若left>right返回空值
int idx = dict[postorder[root]];//取出根节点root在中序序列中的下标
TreeNode* node = new TreeNode(postorder[root]);//新建节点
//递归,idx将原中序序列一分为二,在其左侧的是左子树,右侧的是右子树
node->right = build(root - 1, idx + 1, right, postorder);
//右子树在后序序列上对应的根节点是root - 1,在中序序列上对应的区间是[idx + 1, right]
node->left = build(root - 1 - right + idx, left, idx - 1, postorder);
//左子树在先序序列上对应的根节点是root - 1 - (right - idx)
//在中序序列上对应的区间是[left, idx - 1]
return node;
}
};