根据后序遍历完全二叉树构建树并输出中序遍历

来看这道题:

之前编者想了很久，该如何仅根据后序序列建树，在反复研磨遍历的特征后，我突然发现：

对于完全二叉树，我们完全可以采用其在 线性 ** 表示（用数组）的性质解题

性质:根节点x , 左子树索引为 2x , 右子树索引为 2x+1 且不为空。

则，我们只需按后序遍历的特点递归建树即可。

上代码:

int ind = 0; // 后序序列索引void getPTree(int post[], int index, int N, int result{}){    if(index > N) return; // 超出索引范围    else{ // 按后序的思想        getPTree(post, index<<1, N, result); // 先进行左子树的搭建 index<<1即index*=2        getPTree(post, (index<<1)+1, N, result); // 后进行右子树的搭建        result[index-1] = post[ind++]; // 下标从0开始    }      return; // 搭建完成}

• 后序遍历的特点是：先访问左子树，再访问右子树，最后访问根节点。递归调用 getPTree 时，先递归处理左子树（index << 1），再处理右子树（(index << 1) + 1），最后将当前节点的值填入 result[] 数组。这种递归结构精确模拟了后序遍历的顺序。
• 递归的结束条件是 index > N，即当 index 超过树的节点数时，停止递归，确保不会越界访问。