描述

题目描述

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

示例

输入：{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为队列长度

总结：一般情况，层序遍历通过队列实现，深度遍历通过栈实现