完全二叉树先序中序求后序

### 完全二叉树的先序遍历和中序遍历推导后序遍历

对于完全二叉树而言，可以通过其先序遍历和中序遍历来唯一确定该树结构并进一步获得后序遍历的结果。具体方法如下：

#### 方法概述
由于先序遍历遵循“根-左子树-右子树”的顺序而中序遍历则按照“左子树-根-右子树”，可以利用这两个特性来重建原始二叉树进而得到所需的后序遍历。

#### 实现过程
1. **获取根节点**：从先序序列的第一个元素得知当前子树的根节点。
2. **划分左右子树范围**：依据上述找到的根节点，在中序序列里定位此根的位置从而区分出对应的左右两部分即为原树中的左右子树；
3. **递归处理各分支**：重复以上操作分别针对新的左右子树继续执行直到所有节点都被访问完毕为止；此时即可构建完整的二叉树模型。
4. **生成最终结果**：当整棵树被重构完成后依照定义好的规则——“左子树->右子树->根”依次输出各个顶点形成所期望的后续遍历形式。

下面给出一段Python代码用于展示这一逻辑的具体实现方式:

def build_tree(preorder, inorder):
    if not preorder or not inorder:
        return None
    
    root_val = preorder[0]
    index_in_inorder = inorder.index(root_val)

    left_subtree_size = index_in_inorder 

    root = TreeNode(root_val)
    
    root.left = build_tree(preorder[1:left_subtree_size + 1], inorder[:index_in_inorder])
    root.right = build_tree(preorder[left_subtree_size + 1:], inorder[index_in_inorder + 1:])
    
    return root


class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
def post_order_traversal(node):  
    result = []
    stack = [(node,False)]
      
    while stack:
        node,is_visited = stack.pop()
        
        if node is None:
            continue
            
        elif is_visited:
            result.append(node.val)
            
        else:
            stack.append((node,True))
            stack.append((node.right,False)) 
            stack.append((node.left,False))

    return result

这段程序首先通过`build_tree()`函数基于输入参数preorder(先序列表) 和inorder (中序列表)，自底向上逐步恢复原来的二叉树形态。之后借助辅助类TreeNode表示单个节点的数据成员以及指向下一层级连接关系的信息字段。最后调用`post_order_traversal()`完成对已建好树木对象做一次标准意义上的后序扫描并将沿途遇到的所有数值收集起来作为返回值呈现给用户[^1]。