[Google] Count Complete Binary Tree

Question

link

给定一棵完全二叉树（complete binary tree）的根结点，统计该树的结点总数。

提示：使用O(n)的递归算法统计二叉树的结点数是一种显而易见的方法，此题中请利用完全二叉树的性质，想出效率更高的算法。

Solution

Similar to binary search, O(lgn) complexity.

The idea is, sum up 1 branch of nodes at a time. Do it recursively. The following code is refactored and written by me.

Code

read it from here

//使用TreeNodeUtil.getLeftChildNode(TreeNode)获得左儿子结点
//使用TreeNodeUtil.getRightChildNode(TreeNode)获得右儿子结点
//使用TreeNodeUtil.isNullNode(TreeNode)判断结点是否为空
public class CountCompleteBinayTreeNodes {
    public int countNodes(TreeNode root) {
        if (TreeNodeUtil.isNullNode(root)) {
            return 0;
        }
        int hl = height(TreeNodeUtil.getLeftChildNode(root));
        int hr = height(TreeNodeUtil.getRightChildNode(root));
        if (hl == hr) {
            return (int) Math.pow(2, hl) + countNodes(TreeNodeUtil.getRightChildNode(root));
        } else {
            return (int) Math.pow(2, hr) + countNodes(TreeNodeUtil.getLeftChildNode(root));
        }
    }
    
    private int height(TreeNode root) {
        int count = 0;
        while (!TreeNodeUtil.isNullNode(root)) {
            root = TreeNodeUtil.getLeftChildNode(root);
            count++;
        }
        return count;
    }
}