描述
题目描述
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
示例
输入：{1,2,3,4,5,#,6,#,#,7}
返回值：4引言
求解二叉树相关的题目，一般都可以使用遍历（如层序遍历）或递归（自底向上递归）的方法解决。
知识点：二叉树，分治、遍历、递归
难度：一星
题解
解题思路
该题是典型有关树的统计，很多时候都可以使用递归的次数来计算每个节点的深度，从而计算得到该二叉树根节点的深度
本题的递归方法也可以看作是DFS或后序遍历
也可以使用分治法，分左右子树计算树的高度
方法一：递归（DFS后序遍历）
该题解法既用到递归、后序遍历、深度遍历的思想，还用到了分治法的思想
图解
递归终止条件： 递归到叶子节点
返回值：返回当前节点的深度
递归函数功能：递归函数功能：获取当前节点 root 的深度
算法流程：
本质上是对树作后序遍历
每次递归每个节点 root 的左右子树，并且只得到左右子树中较大的子树深度。
当前节点 root 左右子树递归到叶子节点后，root == null，递归开始自底向上返回，每次向上 return 都 + 1, 即深度 + 1
Java 版本代码如下：
public class Solution {
// 递归函数功能：获取当前节点 root 的深度
public int TreeDepth(TreeNode root) {
// 递归终止条件：递归到叶子节点
if(root == null) {
return 0;
}
// 得到左右子树中较大的子树深度
return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1;
}
} Python 版本代码如下：
class Solution:
// 递归函数功能：获取当前节点 root 的深度
def TreeDepth(self, pRoot):
# 递归终止条件：递归到叶子节点
if pRoot is None:
return 0
# 得到左右子树中较大的子树深度
return max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right)) +1 复杂度分析：
时间复杂度 O(N)：N 为树的节点数量，计算树的深度需要遍历所有节点。
空间复杂度O(N)：N为递归时需要开辟的额外栈空间，用于递归方法堆栈
总结：解决树的很多问题都可以考虑采用递归方法解决，但要注意栈溢出、终止条件问题
方法二：BFS层序遍历
层序遍历也叫广序遍历，对于层序遍历往往通过队列实现，因为需要使用到队列的先进先出的特性，从左到右遍历当前层节点后，需要从下层开始从左到右继续遍历每一个节点，通过此特性实现层序遍历时对树深度的统计
图解
算法流程：
- new一个队列，用于保存每一层的节点，实现bfs
- 遍历每一层，每遍历一层, 计数+1
- queue每次只保存当层的节点数
- 遍历当前层的每一个节点, 队列中poll掉当前层节点, add其所有子节点
- 取出当前节点,并将其左右子节点放入队列
Java 版本代码如下：
import java.util.*;
public class Solution {
public int TreeDepth(TreeNode root) {
if(root == null) return 0;
int res = 0;
// 队列实现bfs
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
// 遍历每一层
while(!queue.isEmpty()) {
// 每遍历一层,计数+1
res++;
// queue每次只保存当层的节点数
int size = queue.size();
// 遍历当前层的每一个节点, 队列中poll掉当前层节点,add其所有子节点
for(int i = 0; i < size; i++) {
// 取出当前节点,并将其左右子节点放入队列
TreeNode node = queue.poll();
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
}
return res;
}
}
Python 版本代码如下：
class Solution:
def TreeDepth(self, pRoot):
# 终止条件
if not pRoot: return 0
queue, res = [pRoot], 0
# 遍历每一层
while queue:
# 存放当前层所有节点的所有子节点
tmp = []
for node in queue:
if node.left: tmp.append(node.left)
if node.right: tmp.append(node.right)
# 随后add进队列，用于下一层遍历
queue = tmp
res += 1
return res复杂度分析：
时间复杂度 O(N)：N 为树的节点数量，层序遍历计算树的深度也要遍历所有节点
空间复杂度O(N)：使用了队列来帮助实现层序遍历，N为队列长度
京公网安备 11010502036488号