二叉树的深度

题目描述

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

例如：

给定二叉树 [3,9,20,null,null,15,7]，

  3
 / \
9  20
  /  \
 15   7

返回它的最大深度 3 。

题解

题意分析

1. 二叉树的深度，指二叉树头节点到最远叶子节点路径中的节点数。
2. 给定根节点，指从根节点开始遍历计算。

深度优先遍历（DFS） + 递归

思路

1. 从头节点开始递归遍历左右子树的深度。
2. 每个节点的深度为左右子树深度的最大值加自身。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

public int maxDepth01(TreeNode root) {
    // 如果节点为空，直接返回深度 0 。
    if (root == null) {
        return 0;
    }
    // 递归返回左右节点的深度。
    int left = maxDepth01(root.left);
    int right = maxDepth01(root.right);
    // 得到左右子树深度的最大值 +1 就是当前节点的深度。
    return Math.max(left, right) + 1;
}

广度优先遍历（BFS） + 队列

思路

1. 按层级遍历二叉树，每遍历一层，二叉树深度 +1 。
2. 遍历完所有层级，返回最终的二叉树深度。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

public int maxDepth02(TreeNode root) {
    // 如果节点为空，直接返回深度 0 。
    if (root == null) {
        return 0;
    }
    // 定义队列，辅助进行广度优先搜索。
    Queue<TreeNode> queue = new LinkedList<>();
    // 从根节点开始遍历。
    queue.add(root);
    int ans = 0;
    while (!queue.isEmpty()) {
        // 每层的节点数。
        int size = queue.size();
        while (size > 0) {
            // 头节点出队，队列长度 -1 。
            TreeNode node = queue.poll();
            size--;
            // 每层遍历将下一层的节点加入队列。
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        // 每遍历完一层，则深度 +1 。
        ans++;
    }
    return ans;
}