[每日一题]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.

题目地址：

https://leetcode.com/problems/count-complete-tree-nodes/题意是求一个二叉树的所有节点的个数。不过这个二叉树有点特别，是一个完全二叉树(complete binary tree)。

wikipedia上关于完全二叉树的定义如下几个特点：

1. 除了最后一层，第n层的节点数等于 2 的 n 次幂（n从0开始，表示的是树的层次）
2. 最后一层的节点的都集中在树的最左边

完全二叉树是一个效率特别高的数据结构，堆是一种完全二叉树或者近似完全二叉树，所以效率也很高。比如一些常用的算法：排序算法，Dijkstra算法等都需要用堆来优化。

思路
这应该是我们首先应该想到的办法，使用经典的搜索方法（深度优先搜索或者广度优先搜索）遍历所有的节点得到结果。

如下是Ruby代码的BFS版本



@M.renard 提交的“一行”代码



暴力法没有利用完全二叉树的特性，所以效率太低了，无法AC。思路

1. 分别求出该树的左分支的最大高度和右分支的最大高度，假设是 left_height和 right_height
2. 比较left_height 和 right_height 的大小
[list=1]
3. 如果 left_height 等于 right_height ，说明该树是一颗完美树（就是说没有空节点），那么节点总数应该满足如下等式:sum  = 2 ** left_height - 1 (解释: 2 的left_height 次幂 减去 1）
4. 如果 left_height 大于 right_height，那么节点总数应该满足如下等式：sum = 1 + sum_of_left + sum_of_rightsum_of_left 是左子树的节点和，sum_of_right 是右子树的节点和这里体现了分治思想，将n的问题分解成了两个n/2的问题，规模变小了。
5. 根据完全二叉树的几个特点，不存在 left_height < right_height 的情况

@洁靖 提交的 C++ 版本



@D@vid 提交的Ruby版本



@东东 提交的Ruby版本

思路

1. 分别求出左子树的left节点的最大高度，右子树的left节点的最大高度，假设是 left_height / right_height
2. 判断 left_height 和 right_height 的大小
[list=1]
3. 如果 left_height > right_height说明 左子树 是一个完美二叉树，其节点总数是 2 ** n - 1 ,  所以结果应该满足如下等式:sum = 2 ** n - 1 + sum_of_right
4. 如果 left_height = right_height说明 右子树 是一颗完美二叉树，其节点总数是 2 ** n - 1, 所以结果应该满足如下等式：sum = sum_of_left + 2 ** n - 1

需要注意的是，这个思路跟上一个思路的区别：
上一个思路，我们求的左右最深节点的深度，这个方案是我们求的左右子树的最左节点的深度。
具体请看代码

如下是 @Jerrold_Gao 的详细解释



@Jerrold_Gao 提交的Java 版



@Jerrold_Gao 提交的Java 版： 优化版本，去掉了很多没有必要的计算，速度快了很多。



@M.renard 提交的Java版本



@Max- 的 python 版本



@东东 的 Ruby 版本

思路
(引用@TK的原话) 循环的时候每次判断左，右子树的高度，如果左子树的高度大于右子树的高度，就往左走，反之往右，同时维护累计的节点数。

想办法走到圈中圈红的那个节点。



@TK 提交的 C++ 版本：

分治算法 + 递归思想的典型应用想加群一起学习算法的小伙伴请关注微信公众号，输入:我要刷题  获取入群的方法。

    关注 一个技术人员的胡言乱语