题目描述

给定一个整数，请输出一个层数为 n 的满二叉树的后序遍历序列。

后序遍历顺序：左 → 右 → 根

输入数据

4

输出数据

894101152121361415731

Limitation

• 时间限制：1 秒
• 内存限制：1024 KiB

题目分析

• 满二叉树 是一种特殊的二叉树，所有节点要么有 0 个子节点（叶子节点），要么有 2 个子节点。
• 需要生成一个高度为 n 的满二叉树并输出其 ​后序遍历结果​。
• 后序遍历的顺序是：​左子树 → 右子树 → 根节点​。

对于高度为 4 的满二叉树，其结构如下：

                1
              /   \
            2       3
          /   \    /   \
        4     5  6     7
       / \   / \ / \   / \
      8  9 10 11 12 13 14 15

• 后序遍历结果就是按照：左 → 右 → 根 顺序遍历每个节点，得到的序列是 8 9 4 10 11 5 2 12 13 6 14 15 7 3 1。