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

前言

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

一、完全二叉树的节点个数

二、抽象二分

package everyday.medium;

// 完全二叉树的节点个数。
public class CountNodes {
    
    /* target：寻找完全二叉树节点个数， 完全二叉树最多有一层没满；最后一层若是没满，也是从左到右有节点，并且每棵子树先左孩子再右孩子。 关键问题：二分找到最后一层的最后一个节点。 每次找到叶子节点logN,以二分的方式找logN,所以时间复杂度O(logN * logN) < O(N)，因为O(logN) < O(sqrt(N)) */
    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 完全二叉树的节点个数