您现在的位置是：首页 >学无止境 >数据结构与算法之二叉树: Leetcode 104. 二叉树的最大深度 (Typescript版)网站首页学无止境

二叉树的最大深度

• https://leetcode.cn/problems/maximum-depth-of-binary-tree/

描述

• 给定一个二叉树，找出其最大深度。

• 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

• 说明: 叶子节点是指没有子节点的节点。

示例

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

      3
     / 
    9  20
      /  
     15   7
  

• 返回它的最大深度 3

算法实现

1 ）方案 1

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function maxDepth(root: TreeNode | null): number {
    let dep = 0;
    // n是节点，l是层级
    const dfs = (n: TreeNode | null, l: number) => {
        if(!n) return;
        // console.log(n.val, l); // 访问当前节点
        (!n.left && !n.right) && (dep = Math.max(dep, l)); // 最大深度和较大层级的最大值, 当为叶子节点时，刷新最大深度
        dfs(n.left, l+1); // 访问左孩子节点
        dfs(n.right, l+1); // 访问右孩子节点
    }
    dfs(root, 1); // 执行
    return dep
};

• 思路
  • 求树的最大深度，考虑使用深度优先遍历
  • 它是按顺序访问每个节点，但是不能拿到最大深度
  • 在深度优先遍历中，记录每个节点所在的层级，找出最大的层级即可
• 步骤
  • 新建一个变量记录最大深度
  • 深度优先遍历整棵树，并记录每个节点的层级，同时不断刷新最大深度这个变量
  • 遍历结束返回最大深度这个变量

2 ）方案 2

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function maxDepth(root: TreeNode | null): number {
    if (!root) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};

• 上述是官方示例，及其简洁
• 注意这个 1 表示当前节点，也是深度优先的递归实现

3 ）方案 3

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function maxDepth(root: TreeNode | null): number {
    if (!root) return 0;
    let q = [root];
    let dep = 0
    while(q.length) {
        let len = q.length; // 当前队列长度
        while(len) {
            const n = q.shift(); // 拿到当前节点
            n.left && (q.push(n.left)) // 左节点进队
            n.right && (q.push(n.right)) // 右节点进队
            len --
        }
        dep ++
    }
    return dep;
}

• 这是官方的C++解题示例，我改造的TS版本
• 使用广度优先遍历实现
  • 此时广度优先搜索的队列里存放的是「当前层的所有节点」
  • 每次拓展下一层的时候，不同于广度优先搜索的每次只从队列里拿出一个节点
  • 需要将队列里的所有节点都拿出来进行拓展，这样能保证每次拓展完的时候
  • 队列里存放的是当前层的所有节点，即我们是一层一层地进行拓展
  • 最后我们用一个变量 dep 来维护拓展的次数
  • 该二叉树的最大深度即为 dep