题目：
Given a complete binary tree, count the number of nodes.
分析：
给定一个完全二叉树的根节点，求该完全二叉树节点的个数。
完全二叉树就是：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。
本题的关键就是求二叉树最后一层的节点个数。对此我们可以使用二分查找。
使用一个整数来表示从根节点到叶子节点的路径，每一位代表方向（0向左，1向右）。例如，1个4层的二叉树，如果路径为5，写成二进制是101，就代表从根节点出发，右，左，右。
通过二分查找，我们可以得到最后一层第一个空节点的位置，也就知道了最后一层有几个几点。然后加上上面几层的节点数就是答案。
代码：
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
public class Solution { public int countNodes(TreeNode root) { if(root == null) return 0; int level = 0; TreeNode p = root; while(p != null){ level++; p = p.left; } if(level == 1) return 1; int lo = 0; int hi = 1 << (level - 1); // Find the position of first null in last level while(lo < hi){ int mi = lo + (hi - lo) / 2; if(access(root, level, mi) == null) hi = mi; else lo = mi + 1; } return (1 << (level - 1)) + lo - 1; } private TreeNode access(TreeNode root, int level, int path){ TreeNode p = root; for(int i = level - 2; i >= 0; i--){ int direction = (path >> i) & 1; if(direction == 0) p = p.left; else p = p.right; } return p; } } |