将一棵二叉树扩充为满二叉树

Question

我只想到一个方法，先计算层数，然后递归往下补，但是感觉效率太低了，请问有没有好一点的方法？

Answer 1

楼主的意思是将二叉树的空节点也表示出来吗？比如说：

               1
              / \
                 3
                / \
               4   5

表示成

               1
             /   \
           nil    3
           / \   / \
          nilnil4  5
          

这样吗。
个人想法满二叉树可以用数组保存，那么楼主可以将数组将二叉树扩充为满二叉树

Answer 2

满二叉树最适合线性存储，所以不必拘泥于原先的存储方法。而且从线性结构恢复为链式结构也很容易。
建立一个大小足够的数组，或者一个可增长的数组，每个元素的初值都是空值。
把根节点存储在下标0的位置；若节点存储在了下标k的位置，那么其左孩子存储在2k+1的位置，右孩子存储在第2k+2的位置。