如果想知道更多的数据结构和算法问题，可以关注Wechat公众号“数据结构和算法”，每天都会有一个问题为你做出精彩的解答。
问题的说明
给出完整的二叉树，求该树的节点数。
说明：
完全二叉树的定义如下。 在完全二叉树中，除了最下层的节点没有被填满的可能性以外，剩下的各层的节点数达到了最大值，最下层的节点集中在该层最左边的几个位置。 如果最下层是第h层，则该层包含1￣2￣h个节点。
样本：
输入：
1
//
2 3
//
4 5 6
输出： 6
1，DFS解决方案
这个问题是求完全二叉树节点数的最简单的方法之一是DFS，也就是递归解决。 如果当前节点为空，则直接返回0即可，否则返回左侧子节点的个数右侧子节点的个数1。 原理比较简单，直接一行代码就可以了
公共节点树{1}
if (树==空值) )。
返回；
queuetreenodequeue=新建链接列表(；
队列添加(树；
while (！ 队列. isempty () )
//poll方法相当于删除队列头的元素
种子节点=队列.保罗(；
system.out.println (节点版)；
//如果左侧的子节点不为空，则将其排队
if (节点左！=空值)
queue.add (节点左；
//如果右子节点不为空，则使他排队
if (节点光！=空值)
队列.添加(节点.写入；
}
}
2，BFS解决
描述了二叉树的几种遍历方法373、数据结构-6、树、前序遍历、中序遍历、后序遍历、BFS、DFS，因为它们各自的写法都包含递归和非递归，所以遍历所有节点每个写一次有点多，在这里用BFS写一个。 二叉树的BFS代码如下。
公共节点树{1}
if (树==空值) )。
返回；
queuetreenodequeue=新建链接列表(；
队列添加(树；
while (！ 队列. isempty () )
//poll方法相当于删除队列头的元素
种子节点=队列.保罗(；
system.out.println (节点版)；
//如果左侧的子节点不为空，则将其排队
if (节点左！=空值)
queue.add (节点左；
//如果右子节点不为空，则使他排队
if (节点光！=空值)
队列.添加(节点.写入；
}
}对其进行改造，数一下节点的数量
公共计数节点(种子根目录)。
if (根==空值) )。
返回0；
int计数=0；
queuetreenodequeue=新建链接列表(；
队列添加(根；
while (！ 队列. isempty () )
//poll方法相当于删除队列头的元素
种子节点=队列.保罗(；
出局； //计算节点的个数
if (节点左！=空值)
queue.add (节点左；
if (节点光！=空值)
队列.添加(节点.写入；
}
返回计数；
}
p>3，从hxdxss找树的高度
题中对完全二叉树的描述已经很清晰了，如果我们还是用上面的两种方式一个个遍历的话，效果明显不是很好，可以考虑下面这种方式
先计算树的高度height，然后计算右子树的高度
1，如果右子树的高度等于height-1，说明hxdxss是满二叉树（如下图所示），可以通过公式(2^(height-1))-1计算即可，不需要全部遍历，然后再通过递归的方式计算右子树……，
2，如果右子树的高度不等于height-1，说明右子树是满二叉树（如下图所示），只不过比上面那种少了一层，也就是height-2，也可以通过公式(2^(height-2))-1计算，然后再通过递归的方式计算hxdxss……，
搞懂了上面的原理，代码就简单多了
public int countNodes(TreeNode root) { //计算树的高度， int height = treeHeight(root); //如果树是空的，或者高度是1，直接返回 if (height == 0 || height == 1) return height; //如果右子树的高度是树的高度减1，说明hxdxss是满二叉树， //hxdxss可以通过公式计算，只需要递归右子树就行了 if (treeHeight(root.right) == height - 1) { //注意这里的计算，hxdxss的数量是实际上是(1 << (height - 1))-1， //不要把根节点给忘了，在加上1就是(1 << (height - 1)) return (1 << (height - 1)) + countNodes(root.right); } else { //如果右子树的高度不是树的高度减1，说明右子树是满二叉树，可以通过 //公式计算右子树，只需要递归hxdxss就行了 return (1 << (height - 2)) + countNodes(root.left); } } //计算树的高度 private int treeHeight(TreeNode root) { return root == null ? 0 : 1 + treeHeight(root.left); }或者我们还可以把它改为非递归的
public int countNodes(TreeNode root) { int count = 0, height = treeHeight(root); while (root != null) { //如果右子树的高度是树的高度减1，那么hxdxss就是满二叉树 if (treeHeight(root.right) == height - 1) {//hxdxss是满二叉树 count += 1 << height - 1; root = root.right; } else {//右子树是满二叉树 count += 1 << height - 2; root = root.left; } height--; } return count; } //计算树的高度 private int treeHeight(TreeNode root) { return root == null ? 0 : 1 + treeHeight(root.left);4，从右子树找树的高度
上面是先计算二叉树的高度，它是从左子节点一直往下走，找到树的高度。还可以换种思路从树的右子节点往下走，找到树的高度，原理都差不多，代码中有详细注释，就不在过多介绍
public int countNodes(TreeNode root) { if (root == null) return 0; //计算高度，注意这里不是树的实际高度 int height = treeHeight(root); if (treeHeight(root.left) == height) {//hxdxss是满二叉树，通过公式计算 return (1 << height) + countNodes(root.right); } else {//右子树是满二叉树，通过公式计算 return (1 << height - 1) + countNodes(root.left); } } //计算树的高度，注意这个结果不是树的实际高度，如果树是满二叉树，他就是树的 //高度，如果不是满二叉树，他就是树的高度减1 private int treeHeight(TreeNode root) { return root == null ? 0 : 1 + treeHeight(root.right);//注意这里遍历的是树的右结点5，总结
二叉树的遍历方式除了之前讲373，数据结构-6,树中的前序，中序，后续，以及BFS以外，还有莫里斯的前中后3种遍历方式。这些遍历方式有的还包含递归以及非递归等多种写法，如果都写一遍的话答案就非常多了。但这里说的是完全二叉树，我们可以根据完全二叉树的特性来计算，没必要把所有的节点都要遍历一遍。
二叉树常见的几种遍历方式（包括前序，中序，后序，DFS，BFS）在第373题都有过介绍，并且都有递归和非递归等多种实现方式。关于二叉树的莫里斯（Morris）的3种遍历方式后面有时间也会做介绍，期待大家一块学习。