算法

(二分查找) $O(log^2h)$

本题可以利用完全二叉树的特性，也就是它的空节点只会出现在最后一层，而上面的都是满的，而对于最后一层为空的节点都在右侧，它的左侧全部都不为空。于是这个问题就变成了最后一层之上的节点个数以及最后一层的节点个数，对于第一个问题，若求出树的高度后可以用$O(1)$的复杂度解决，即高度为$h$的树，它的节点个数为$2^h-1$；而对于第二个问题，我们可以把最后一行看成一个数组，由最后一行的节点个数也是有一个范围的，我们想要找到最后一个不为空的节点，而这个$index+1$就是不为空的节点的个数了，也就是在一个数组中找一个$target$，于是我们可以二分。

Java 代码

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int h = 0;
        TreeNode node = root;
        while (node.left != null) {
            h++;
            node = node.left;
        }

        int upper = (1 << h) - 1;
        int start = 0, end = upper;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (hasNode(root, mid, h)) {
                start = mid;
            }
            else {
                end = mid;
            }
        }
        if (hasNode(root, end, h)) {
            return upper + end + 1;
        }
        return upper + start + 1;
    }

    public boolean hasNode(TreeNode root, int idx, int h) {
        int start = 0;
        int end = (1 << h) - 1;
        TreeNode node = root;
        for (int i = 0; i < h; ++i) {
            int mid = start + (end - start) / 2;
            if (mid >= idx) {
                node  = node.left;
                end = mid;
            }
            else {
                node = node.right;
                start = mid;
            }
        }
        return node != null;
    }
}