本文共 1764 字，大约阅读时间需要 5 分钟。

1. 本题知识点

树

2. 题目描述

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

3. 解题思路

求树的深度，可以从层次遍历出发考虑。

层次遍历可以使用队列完成，也可以使用递归完成，所以有两种解题思路。

递归

1. 如果当前结点为空，返回 0
2. 如果不为空，返回其左子树和右子树中深度最大的值再加 1

使用队列

1. 创建深度，初始化为 0
2. 创建一个队列
3. 将根节点加入队列
4. 当队列不为空时，执行以下循环
   1. 记录本层二叉树的结点数
   2. 当本层二叉树的结点数大于 0，执行以下循环
      1. 删除队头
      2. 将删除的队头的左右子树加入队尾
      3. 本层二叉树结点树减 1
   3. 深度加 1
5. 最后返回深度

4. 代码

递归

public class TreeNode {
       int val = 0;    TreeNode left = null;    TreeNode right = null;    public TreeNode(int val) {
           this.val = val;    }}

public class Solution {
       public int TreeDepth(TreeNode root) {
           if (root == null) {
               return 0;        }        return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1;    }}

使用队列

public class TreeNode {
       int val = 0;    TreeNode left = null;    TreeNode right = null;    public TreeNode(int val) {
           this.val = val;    }}

import java.util.LinkedList;import java.util.Queue;public class Solution {
       public int TreeDepth(TreeNode root) {
           // 深度        int depth = 0;        // 创建一个队列        Queue
   
     queue = new LinkedList<>();        // 将根节点加入队列        if (root != null) {
               queue.add(root);        }        // 队列不为空，执行循环        while (!queue.isEmpty()) {
               // 二叉树本层结点数            int count = queue.size();            while (count > 0) {
                   // 删除队头结点，将其左右子树加入队列                TreeNode remove = queue.remove();                if (remove.left != null) {
                       queue.add(remove.left);                }                if (remove.right != null) {
                       queue.add(remove.right);                }                // 二叉树本层结点数减 1                count--;            }            // 深度加 1            depth++;        }        return depth;    }}
   

转载地址：http://vyjvb.baihongyu.com/