[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;
	}
}