二叉树的最大深度

• 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 = 0while(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