求二叉树深度算法（深度优先、广度优先）_广度优先求树的深度

求二叉树深度

注：本文中二叉树通过二叉链表构建。
节点类型定义如下：

struct node{
	char data;
	node *lchild;
	node *rchild;
};
1
2
3
4
5

方法一：深度优先的遍历方式

思路一（自上向下）：每下一层，就和当前暂存的最大的深度作比较并取最大值

对二叉树做遍历操作，最简单可以用递归的方式实现。
这就需要我们对递归进行下一层的时候，需要记录下一层的深度等于当前深度+1。

通过递归实现后的代码如下：

int maxDeep = 0; //暂存的最大深度
void MaxDeep(node* root, int nowDeep){
	if (root == NULL){//递归结束条件，说明这一层已经不是二叉树的节点，也就不需要使nowDeep和maxDeep进行比较
		return;
	}
	
	maxDeep = max(maxDeep, nowDeep);//取较大值
	MaxDeep(root->lchild, nowDeep+1);//递归处理左子树
	MaxDeep(root->rchild, nowDeep+1);//递归处理右子树
}
1
2
3
4
5
6
7
8
9
10

需要注意的是，调用时，根节点的深度为一，即nowDeep传1。

思路二（自下向上）：当前树的最大深度等于其子树的最大深度+1
在第一种思路中，我们需要借助一个额外的变量maxDeep去记录当前处理过的最大深度，这是一个外部变量，当然可以放到形参里面，但是一个对递归没有什么作用的数作为一个形参出现就会显得有些奇怪，用起来也不方便。

为了方便使用，我们可以换一种思路：
既然自上向下的路走不通，可以反过来走。

对于一棵二叉树，可以根据有无父节点分为“根节点”和“非根节点”，对于每个“非根节点”又可以作为一棵新的树的根节点。那么这种思路反过来，就有了：
当前树的最大深度等于其子树的最大深度+1。这里的“1”是根节点自己还有一层深度需要加上。

以这种思路实现的代码：

int maxDeep(node* root){
	if(root == NULL){//递归到叶子节点的“子树”，不存在，其深度为0，递归结束。
		return 0;
	}
	return max(maxDeep(root->lchild),maxDeep(root->rchild))+1;//如果有子树，其深度为左右子树的最大值+1。
}
1
2
3
4
5
6

这个代码还可以简写成：

int maxDeep(node* root){
	return root == NULL ? 0 : max(maxDeep(root->lchild),maxDeep(root->rchild))+1;
}
1
2
3

方法二：广度优先的遍历方式

深度优先的方式是一路走到黑，记录路径长度。
那么广度优先的方式就是真真正正的计算层次来得到二叉树的深度了。

这里用到了二叉树的层次遍历的思路
实现代码：

struct que{//只是封装了队列节点类型，并没有自己封装队列，可以使用STL的queue进行操作
	node* root;
	int index;
}; 

int maxDeep(node* root){
	que q[505];
	for (int i = 0;i < 505; i++){//初始化
		q[i].root = NULL;
		q[i].index = 0;
	}
	//层次遍历
	int head = 0;
	int tail = 1;
	q[tail].root = root;//根节点入队
	q[tail].index = 1;
	while (head != tail){
		head++;//当然也可以写成环形队列的方式
		if (q[head].root->lchild != NULL){//其左子树不为空
			tail++;
			q[tail].root = q[head].root->lchild;//左子树入队
			q[tail].index = q[head].index+1;//记录其左子树的根节点所在层数为该节点层数+1
		}
		if (q[head].root->rchild != NULL){//其右子树不为空
			tail++;
			q[tail].root = q[head].root->rchild;//右子树入队
			q[tail].index = q[head].index+1;//记录其右子树的根节点所在层数为该节点层数+1
		}
	}
	return q[tail].index;//做到最后就是最深的一层，即为二叉树的深度
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

总结

• 两种方法各有优劣，深度优先的方法使用了递归的方式进行实现，对时间和空间的消耗都是较大的，但编码复杂度极低；广度优先的方法则相反，对时间空间的消耗较小，但编码复杂度较高。
• 深度优先的方式可以不适用递归的方式进行，需要手动用栈进行模拟递归，对系统时间和空间的消耗有所改善，但编码复杂度将会提高，需要自行进行取舍。
• 在广度优先的方式实现时没有对队列进行封装，同时可以使用C++ STL的queue进行实现。