LeetCode #222 Count Complete Tree Nodes (完全二叉树节点个数)

题目:

Given a complete binary tree, count the number of nodes.

 

分析:

给定一个完全二叉树的根节点,求该完全二叉树节点的个数。

完全二叉树就是:除最后一层外,每一层上的节点数均达到最大值;在最后一层上只缺少右边的若干结点。

本题的关键就是求二叉树最后一层的节点个数。对此我们可以使用二分查找。

使用一个整数来表示从根节点到叶子节点的路径,每一位代表方向(0向左,1向右)。例如,1个4层的二叉树,如果路径为5,写成二进制是101,就代表从根节点出发,右,左,右。

通过二分查找,我们可以得到最后一层第一个空节点的位置,也就知道了最后一层有几个几点。然后加上上面几层的节点数就是答案。

 

代码:

Java