完全二叉树的节点个数[非O(n)求法 -＞ 抽象二分]

• 前言
• 一、完全二叉树的节点个数
• 二、抽象二分
• 总结
• 参考文献

抽象二分无处不在，以快速砍掉一半无用数据，从而降低时间复杂度。
将二分判定的规则抽象，则二分可灵活的应用到多种场景种。
以 O(logN * logN) < O(N) 的低时间复杂度来求完全二叉树的节点个数。

package everyday.medium;

// 完全二叉树的节点个数。
public class CountNodes {
    
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        // 确定树高。
        int hLeft = getLevel(root);
        // 二分
        // int width = (int) Math.pow(2, hLeft - 1);
        // 看了别人的评论，针对2的多少次方，可用位运算替代。
        int width = 1 << hLeft - 1;
        int low = 0, high = width - 1;
        while (low < high) {
        	// 配合low = mid,防止死循环。
            int mid = low + (high - low + 1 >>> 1);

            int level = hLeft;
            int sum = 0;
            TreeNode p = root;
            while (level-- > 1) {
                if ((sum + (1 << level - 1)) > mid) p = p.left;
                else {
                    sum += 1 << level - 1;
                    p = p.right;
                }
            }
            // 寻找最后一个节点。
            if (p == null) high = mid - 1;
            else low = mid;
        }
        // 计算总节点数。去掉最后一层的节点数 + 最后一层的节点数
        return (int) ((1 << hLeft - 1) - 1) + (low + 1);
    }

    // 确定树左深度。
    private int getLevel(TreeNode root) {
        int h = 0;
        while (root != null) {
            ++h;
            root = root.left;
        }
        return h;
    }

    // Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}

1）完全二叉树。
2）以 O(logN * logN) 的方式来得到完全二叉树的节点数。
3）抽象二分 + 如何以 O(logN) 找到完全二叉树的第 N 个叶子节点。

[1] LeetCode 完全二叉树的节点个数