Leetcode 222. Count Complete Tree Nodes

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.

Next challenges: Closest Binary Search Tree Value

思路：题目要求的是计算完全二叉树的总节点数。假设完全二叉树的树高是n（n>0），并且树是满的，那么树的总节点是2^(n)-1。

首先想到的是O(n)的遍历每个节点的方案，但是这个方案会出现"Time Limit Exceeded"错：

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public int countNodes(TreeNode root) {
12         if (root == null) {
13             return 0;
14         }
15         return countNodes(root.left) + countNodes(root.right) + 1;
16     }
17 }

思路一：注意到完全二叉树中，最后一层的最后一个叶子结点要么在左子树，要么在右自树上，这就说明左右子数至少有一棵是满的完全二叉树。因此只要不断遍历当前子树的根的左子树，不断遍历根的右子树，如果最后两边都遍历到null，说明该子树是满的，计算出子树树高h，只要返回2^(h)-1就是子树包含的总节点数。

代码：

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public int countNodes(TreeNode root) {
12         int height = 0;
13         TreeNode right = root;
14         TreeNode left = root;
15         while(right != null) {
16             left = left.left;
17             right = right.right;
18             height++;
19         }
20         if(left == null) {//判断当前子树是否为满的完全二叉树
21             return (1<<height) - 1;
22         }
23         return 1 + countNodes(root.left) + countNodes(root.right);
24     }
25 }

时间复杂度：O(log(n)*log(n))

T(n) = T(n/2) + c1 lgn = T(n/4) + c1 lgn + c2 (lgn - 1) = ... = T(1) + c [lgn + (lgn-1) + (lgn-2) + ... + 1] = O(lgn*lgn)

思路二：注意到完全二叉树的节点总数和树高是有关联的。如果左子树和右子树的树高相同，则说明最后的叶节点在右子树，那么可以先根据完全二叉树节点计算公式先计算左子树的节点总数+1，然后再递归计算右子树的节点数；如果左子树和右子树的树高不同，说明最后的叶节点在左子树，那么可以先根据完全二叉树节点计算公式先计算右子树的节点总数+1，然后再递归计算左子树的节点数。

代码：

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public int height(TreeNode root) {//子树的根为空，则树高为0
12         return root == null ? 0 : 1 + height(root.left);
13     }
14     public int countNodes(TreeNode root) {
15         int h = height(root);
16         return h == 0 ? 0 : 
17             h - 1 == height(root.right) ? 
18                 (1<<(h - 1)) + countNodes(root.right)//最后的叶子节点在右子树，左子树是满的，那么只要求右子树的节点数
19                 : (1<<(h - 2)) + countNodes(root.left);//最后的叶子节点在左子树，右子树是满的，那么只要求左子树的节点数
20     }
21 }

时间复杂度：O(log(n)*log(n))