Given a complete binary tree, count the number of nodes.
Definition of a complete binary tree from Wikipedia: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
首先，不管是满二叉树还是完全二叉树，一直往左遍历都能得到树的高度。第一种方法，采用递归，思路是满二叉树的节点数等于2^h-1。代码如下： /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int countNodes(TreeNode root) { if (root == null) { return 0; } TreeNode left = root, right = root; int hight = 0; while (right != null) { left = left.left; right = right.right; hight ++; } if (left == null) { return (1 << hight) - 1; } return 1 + countNodes(root.left) + countNodes(root.right); } }第二种还是递归，思路是先侦查右树高度，方法是沿着根节点右节点一路向左下找，如果右树高度是h，那么左树肯定是满树，节点数是2^(h-1)，再继续侦查右树，如果右树高度是h-1，说明左树不满，右树是满树，且节点数是2^(h - 2)，再继续侦查左树。代码如下： class Solution { int height(TreeNode root) { return root == null ? -1 : 1 + height(root.left); } public int countNodes(TreeNode root) { int h = height(root); return h < 0 ? 0 : height(root.right) == h-1 ? (1 << h) + countNodes(root.right) : (1 << h-1) + countNodes(root.left); } }第三种是上一种方法的迭代版，省去了每次计算全树的高度。代码如下： class Solution { int height(TreeNode root) { return root == null ? -1 : 1 + height(root.left); } public int countNodes(TreeNode root) { int nodes = 0, h = height(root); while (root != null) { if (height(root.right) == h - 1) { nodes += 1 << h; root = root.right; } else { nodes += 1 << h-1; root = root.left; } h--; } return nodes; } }