题目： 给出一个完全二叉树，求出该树的节点个数。
说明：
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1 − 2 h {1-2^h} 1−2h 个节点。
示例: 输入: 1 / \ 2 3 / \ / 4 5 6 输出: 6题解： 二分搜索方法： 完全二叉树中，除了最后一层外，其余每层节点都是满的，并且最后一层的节点全部靠向左边。
计算二叉树的深度d(从0开始计算)，除了最后一层，上层的节点数量为 2 d − 1 {2^d-1} 2d−1最后一层节点全部靠向左边，从左到右，判断privot这个节点是否存在，如果存在，那么最后一个节点在 p r i v o t − 2 d privot-2^d privot−2d后半部分，如果不存在，最后一个节点在 1 − p r i v o t 1-privot 1−privot所在的前半部分，循环迭代二分法，得到最后一个节点所在的位置即可。java代码：
/** * 二分查找方式 * * @param root * @return */ public static int countNodes3(TreeNode root) { if (root == null) return 0; int depth = getDepth2(root); if (depth == 0) return 1; int countNode = (int) Math.pow(2, depth) - 1; int lastnodes = (int) Math.pow(2, depth); int left = 1, right = lastnodes; int lastNum = 0; while (left <= right) { int privot = left + (right - left) / 2; if (isExist2(privot, depth, lastnodes, root)) { lastNum = privot; left = privot + 1; } else { right = privot - 1; } } return countNode + lastNum; } /** * 获取二叉树的深度，第一行从0开始 * @param root * @return */ public static int getDepth2(TreeNode root) { int dep = -1; TreeNode node = root; while (node != null) { dep++; node = node.left; } return dep; } /** * 判断节点是否存在 * @param privot * @param depth * @param lastnode * @param root * @return */ public static boolean isExist2(int privot, int depth, int lastnode, TreeNode root) { int left = 1, right = lastnode; for (int i = 0; i < depth; i++) { int mid = left + (right - left) / 2; if (privot <= mid) { root = root.left; right = mid; } else { root = root.right; left = mid + 1; } } if (root == null) return false; return true; }