根据先序序列和中序序列重建二叉树(详细注释)
题目描述
本题代码参考leetcode题解,题解链接附录在下方。
给定先序序列和中序序列,在不考虑递归的情况下,根据先序和中序的遍历顺序我们可以将其分别划分:
先序序列:[根节点 | 左子树 | 右子树];
中序序列:[左子树 | 根节点 | 右子树];
本题的核心思想是:
1)由先序序列确定根节点;
2)在中序序列中找到此根节点(无重复元素)
3)中序序列根节点左侧节点数量(元素数量)即为左子树上元素数量;右子树同理;
4)由先序遍历性质可知,在左子树存在的情况下,先序序列中根节点索引 + 1即为左子树根节点的索引;
在右子树的存在的情况下,根节点索引 + (左子树长度 + 1)即为右子树根节点索引。
5)根据(3)、(4)获得左子树的根节点索引与左子树对应序列的范围 和 右子树的根节点索引与右子树对应
序列的范围;
6)递归。
原题解链接
C++ 代码
class Solution {
public:
unordered_map<int, int> dic;//创建哈希表存储中序序列中元素对应的下标
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int len = inorder.size();
for(int i = 0; i < len; i ++ ){
dic[inorder[i]] = i;//存储
}
//先序序列的根节点一定从0开始
return Pre_In_build(0, 0, len - 1, preorder);
}
TreeNode* Pre_In_build(int root, int left, int right, vector<int>& preorder){
//root是先序序列中的索引,left、right是中序序列的索引
if(left > right)return NULL;//若left==right当前节点是叶子结点,若left>right返回空值
int idx = dic[preorder[root]];//取出根节点root在中序序列中的下标
TreeNode* node = new TreeNode(preorder[root]);//新建节点
//递归,idx将原中序序列一分为二,在其左侧的是左子树,右侧的是右子树
node->left = Pre_In_build(root + 1, left, idx - 1, preorder);
//左子树在先序序列上对应的根节点是root + 1,在中序序列上对应的区间是[left, idx - 1]
node->right = Pre_In_build(root + 1 + idx - left, idx + 1, right, preorder);
//右子树在先序序列上对应的根节点是root + 1 + idx - left;在中序序列上对应的区间是[idx + 1, right]
return node;
}
};