P3606. 完全二叉树非叶子部分后序遍历

解题思路

关于二叉树的基础内容可以详见二叉树专题小班里的内容。

本题分为两个部分，一是根据输入还原出这棵完全二叉树，二是根据这棵完全二叉树输出后序遍历（不包含叶子节点）的结果。

还原完全二叉树

二叉树的节点类使用最普通的构造方法即可，包含左节点、右节点、值三个成员变量。

容易发现：对于一棵完全二叉树，在给定输入数组 lst 作为层序遍历的结果时，该数组中索引为 i 的节点，其左、右节点在 lst 中的索引为 2*i+1 和 2*i+2。

譬如对于例子

构建出的完全二叉树如下

需要特别注意的是，只有当 2*i+1 或 2*i+2 没有超出 lst 数组索引范围的时候，left 或 right 节点才存在，因此容易得到关系

如果我们想构建出一个值为 val 的当前节点 cur，可以构建出如下的构建函数 buildNode()

注意到，上述函数只能构建出当前节点 cur 的情况，将 cur 和 left、right 进行连接。但是 left 和 right 它们更下一层的左右节点连接情况，是无法从上述函数中体现出来的。

所以我们需要把这个函数设计成一个递归函数，来获得整棵树的连接关系。

这个函数返回的是，构建完毕的当前节点 cur。如果我们把构建左、右节点的函数换成递归函数，传入各自在 lst 中的索引 2*i+1 和 2*i+2，那么递归函数会返回 left 或者 right 构建情况。这样就可以将整棵树的连接关系得到了。即

换句话说，我们就解决了递归子问题：得到具有连接关系的左、右节点，并且构建当前节点，将左、右节点和当前节点连接。这个递归子问题，对于左、右节点而言也是同样需要考虑和执行的。这是一个自底向上的递归，因为我们总是先执行左、右子树的递归函数，最后才构建 cur。

如果嫌上述递归函数还太长，还可以继续优化上述函数。譬如

甚至一行写完

对应的递归入口调用也非常简单，即

就能得到根节点 root 了。

非叶子部分的后序遍历

普通的后序遍历，相信大家都非常熟悉了，即使用左-右-根的顺序来递归地访问节点。

由于题目要求考虑的是非叶子部分的后序遍历，也就是说当一个节点是叶子节点的时候，其值不应该出现在后序遍历结果数组 ans 中。因此我们可以在上述函数中再加入一个判断，当节点不是叶子节点的时候，才将 node.val 的结果加入到 ans 中。即

综上本题基本就解决了。

复杂度分析 设输入的整数个数为 n（题面约定最多 1000 个）。

• 还原完全二叉树 buildNode：每个数组下标 i 恰好对应一次递归调用，调用内只做下标越界判断和节点构造这些常数量工作，故为 O(n)。
• 非叶子部分后序遍历 postorder：每个节点被访问一次，判断左右孩子是否存在为 O(1)，为 O(n)。
• 拼接并输出结果为 O(n)。

总时间复杂度 O(n)，瓶颈是建树与遍历这两趟对全部节点的线性处理。空间复杂度 O(n)：还原出的 n 个节点对象占 O(n)；由于按完全二叉树的下标关系（i 的孩子在 2i+1、2i+2）递归，递归深度等于树高，完全二叉树的树高为 O(log n)，因此建树与遍历两段递归的栈开销都只有 O(log n)，结果数组 ans 另占 O(n)。