在数据结构课程的学习中,我们知道前序or后序+中序的组合可以确定一棵树,而前序+后序则可能会有多棵不同的树。下面就这两大类问题展开讨论。(以下讨论的树每一个结点的值都不相同)
前序or后序+中序 PAT1127
在能够确定树的情况下,常常会要求我们建树。此时的思路就是不断确定每段序列中根节点的位置,而后分别递归建立左右子树。函数输入中序和后序序列开始和结束的位置。
由于知道后续的最后一个节点是根节点,因此在中序中找到和这个相同的节点,并以此划分序列,左右递归建树即可。
TreeNode * build(TreeNode * r, int inBg, int inEd, int postBg, int postEd){
if (inBg > inEd){
return nullptr;
}
if (inBg == inEd){
r = new TreeNode();
r->val = in[inBg];
return r;
}
int i = inBg;
while (i < inEd && in[i] != post[postEd]){
i++;
}
r = new TreeNode();
r->val = post[postEd];
r->left = build(r->left, inBg, i - 1, postBg, postBg + (i - inBg) - 1);
r->right = build(r->right,i + 1, inEd, postBg + (i - inBg), postEd - 1);
return r;
}
前序+后序 PAT1119
和前一种一样,我们需要确定哪些部分是左孩子,那些是右孩子。通过寻找前序遍历中和后序遍历根节点前的一个节点相同的节点来划分。此时此需要判断在什么情况下可能不唯一。
答案就是如果前序遍历根节点后的第一个节点,等于后序遍历根节点前的一个节点,会出现多解。因为不知道这个节点是单个的左孩子节点,还是左子树为空直接作为右孩子节点。
这里按照中序遍历的顺序对节点操作。并把不确定的情况,直接当成右孩子节点。若需要找到所有可能的树,则需要再对作为左孩子的情况进行讨论。
void getIn(int preBg, int preEd, int postBg, int postEd){
if (preBg == preEd){
tree.push_back(pre[preBg]);
return;
}
if (pre[preBg] == post[postEd]){
int i = preBg + 1;
while(i < preEd && pre[i] != post[postEd - 1]){
i++;
}
if (i == preBg + 1){
flag = 1;
}
else
getIn(preBg + 1, i - 1, postBg, postBg + (i - preBg - 1) - 1);
tree.push_back(pre[preBg]);
getIn(i, preEd, postBg + (i - preBg - 1), postEd - 1);
}
}