博文中会简要介绍Leetcode P0222题目分析及解题思路。
“Count Complete Tree Nodes”是一道比较有意思的题目。这道题最简单的想法是用深度优先搜索或者广度优先搜索遍历一遍整个树，然后就可以统计出结点的个数。但是这道题还有一种比较巧妙的方法，并且这个方法的思想十分值得我们去借鉴和学习。
我们可以利用完全二叉树的性质，即一棵树除了最深一层外是一颗满二叉树，而最深一层的结点个数n满足1<=n<=2^h，其中h是树的最大高度。这种性质使得我们只需要得到最深层（深度为h时）的结点个数n。换句话说，我们只需要知道在深度h从哪个结点开始为空叶子结点即可。这样一来我们可以利用二分查找，找到最末的那个空叶子结点。
Given a complete binary tree, count the number of nodes.
Note:
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.
Example:
Input: 1 / \ 2 3 / \ / 4 5 6 Output: 6
首先我们讲解线性时间的方法，即时间复杂度为O(n)。我们可以使用深度优先搜索，访问每个结点，若结点为空，则返回0，否则返回1与下层返回值的和。
以下是Java的题解代码实现。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int countNodes(TreeNode root) {
return this.count(root);
}
private int count(TreeNode node) {
if (node == null)
return 0;
return 1+this.count(node.left)+this.count(node.right);
}
}
接着我们讲解第二种解法，这种方法的时间复杂度是O(d^2)，其中d是这棵树的最大深度，也就是说d=logn。
简要来说，这种解法的核心思想是利用二分查找，观察pivot的位置是不是空叶子结点，如果是则缩小右边界，否则缩小左边界。那么如何找到pivot位置上的结点呢？我们需要再利用一次二分查找的思想，若pivot在当前二分点左边，我们向左子树移动；若pivot在当前二分点右边，我们向右子树移动，如此递归即可找到pivot上的结点。
这种解法的具体思路已经在下面的代码中详细注释，可以参考借鉴。
以下是第二种解法的Java的题解代码实现。
class Solution {
// Return tree depth in O(d) time.
public int computeDepth(TreeNode node) {
int depth = 0;
while (node.left != null) {
node = node.left;
++depth;
}
return depth;
}
// Last level nodes are enumerated from 0 to 2**d - 1 (left -> right).
// Return True if last level node idx exists.
// Binary search with O(d) complexity.
public boolean exists(int idx, int depth, TreeNode node) {
int left = 0, right = (int) Math.pow(2, depth) - 1, pivot = 0;
for(int i = 0; i < depth; ++i) {
pivot = left + (right - left) / 2;
if (idx <= pivot) {
node = node.left;
right = pivot;
}
else {
node = node.right;
left = pivot + 1;
}
}
return node != null;
}
public int countNodes(TreeNode root) {
// if the tree is empty
if (root == null)
return 0;
int d = computeDepth(root);
// if the tree contains 1 node
if (d == 0)
return 1;
// Last level nodes are enumerated from 0 to 2**d - 1 (left -> right).
// Perform binary search to check how many nodes exist.
int left = 1, right = (int) Math.pow(2, d) - 1, pivot = 0;
while (left <= right) {
pivot = left + (right - left) / 2;
if (exists(pivot, d, root))
left = pivot + 1;
else
right = pivot - 1;
}
// The tree contains 2**d - 1 nodes on the first (d - 1) levels
// and left nodes on the last level.
return (int) Math.pow(2, d) - 1 + left;
}
}
同样地，和第一种解法类似，线性时间内我们可以使用层遍历，即广度优先搜索来访问每一个结点，最终得到结点总数。
以下是C++的题解代码实现。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int countNodes(TreeNode* root) {
if (!root)
return 0;
queue<TreeNode*> node_queue;
node_queue.push(root);
int count = 0;
while (!node_queue.empty()) {
TreeNode *curr = node_queue.front();
node_queue.pop();
if (curr->left)
node_queue.push(curr->left);
if (curr->right)
node_queue.push(curr->right);
++count;
}
return count;
}
};