[Google] Count Complete Binary Tree

link

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