1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
    /**
     * 创建一颗树高为 treeHeight 的完全二叉树
     *
     * @param treeHeight 树高
     * @return 以数组形式存储的完全二叉树,第一个位置为空
     */
    public static byte[] constructTree(int treeHeight) {
        // 计算数组所需要的长度
        int arrLength = 1 << treeHeight;
        // 创建数组
        byte[] tree = new byte[arrLength];
        // 数组下标从 1 开始,0 位置空出来
        // 控制数组的下标,使其一直向前移动
        int index = 1;
        // 按层遍历
        for (int heightIndex = 0; heightIndex < treeHeight; heightIndex++) {
            // 计算每层有多少个位置
            int treePit = 1 << heightIndex;
            // 遍历每层上面的每个位置,然后向里面放入值
            for (int pitIndex = 0; pitIndex < treePit; pitIndex++) {
                // 给每个位置赋值
                tree[index] = (byte) heightIndex;
                // 控制数组下标向前移动
                index++;
            }
        }
        return tree;
    }

    // 测试用例
    public static void main(String[] args) {
        int treeHeight = 3;
        System.out.println(Arrays.toString(constructTree(treeHeight)));
        // [0, 0, 1, 1, 2, 2, 2, 2]
    }

上述代码构造出来的二叉树如下图所示