计算左子树规模（结点个数），找出树的根结点

编辑

1.完美二叉树总结点数为 编辑

2.我们要计算一棵树有多少层，则可以分成完美二叉树 编辑

和最下层结点个数X 编辑这两部分，层数通过求log来计算

编辑

因为X不影响计算，所以可以把它去掉，然后向下取整，得出H的值 编辑

3.此时我们就可以从红色三角处开始计算左子树个数 编辑

由图可知，在树的最后一层可以没有任何结点，形成完全二叉树，X最小值就可以取为0；

图中这棵树有三个结点，X即为3；

最大值就参考计算第一部分完美二叉树每一层结点数公式 编辑

要求的是左子树的X部分，所以左边部分结点只有处于满结点时的一半，由图可以看出，可以直接视为上一层的最大结点数

编辑

当X小于 编辑时，左子树最后一层的X就是此值；

当X大于 编辑时，最大就只能取到 X= 编辑

所以有 编辑

4.最后一步，我们将左边红色三角这块完美二叉树结点数+X，就能得到左子树的结点个数了

此时我们在数组中找到 左子树结点数+1 所对应的那个元素就是我们的根结点了

编辑

假设左子树结点数为5，这棵树的根结点就为5+1=6，即第二个8为根结点