题目：
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 2hnodes inclusive at the last level h.
思路：
Full v.s. Complete Binary Trees
According to wikipedia
A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
Steps to solve this problem:1) get the height of left-most part2) get the height of right-most part3) when they are equal, the # of nodes = 2^h -14) when they are not equal, recursively get # of nodes from left&right sub-trees
Time complexity is O(h^2).
代码：
1 public int countNodes(TreeNode root) { 2 if(root==null) 3 return 0; 4 5 int left = getLeftHeight(root)+1; 6 int right = getRightHeight(root)+1; 7 8 if(left==right){ 9 return (2<<(left-1))-1; 10 }else{ 11 return countNodes(root.left)+countNodes(root.right)+1; 12 } 13 } 14 15 public int getLeftHeight(TreeNode n){ 16 if(n==null) return 0; 17 18 int height=0; 19 while(n.left!=null){ 20 height++; 21 n = n.left; 22 } 23 return height; 24 } 25 26 public int getRightHeight(TreeNode n){ 27 if(n==null) return 0; 28 29 int height=0; 30 while(n.right!=null){ 31 height++; 32 n = n.right; 33 } 34 return height; 35 }
reference：http://www.programcreek.com/2014/06/leetcode-count-complete-tree-nodes-java/
转载于:https://www.cnblogs.com/hygeia/p/4772126.html
相关资源：JAVA上百实例源码以及开源项目