leetcode:二叉树的最大深度

题目描述

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

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

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

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

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

题目链接：104. 二叉树的最大深度

思路

由于树是一种递归的数据结构，因此用递归去解决的时候往往非常容易。

用递归实现的代码如下：

var maxDepth = function (root) {

    if (!root) return 0;

    if (!root.left && !root.right) return 1;

    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));

};

二叉数的遍历主要有前中后遍历和层次遍历。 前中后属于 DFS，层次遍历则可以使用 BFS 或者 DFS 来实现。只不过使用 BFS 来实现层次遍历会容易些。

对于此题我们首先应该想到的是树的各种遍历，由于我们求的是深度，因此 使用层次遍历（BFS）是非常合适的。 我们只需要记录有多少层即可。

关键点：

• 队列
• 队列中用 Null(一个特殊元素)来划分每层，或者在对每层进行迭代之前保存当前队列元素的个数（即当前层所含元素个数）
• 树的基本操作- 遍历 - 层次遍历（BFS）

代码：

var maxDepth = function (root) {
    if (!root) return 0;
    if (!root.left && !root.right) return 1;
    // 层次遍历 BFS
    let cur = root;
    const queue = [root, null];
    let depth = 1;
    while ((cur = queue.shift()) !== undefined) {
        if (cur === null) {
            // 注意： 不处理会无限循环，进而堆栈溢出
            if (queue.length === 0) return depth;
                depth++;
                queue.push(null);
                continue;
            }

            const l = cur.left;
            const r = cur.right;
            if (l) queue.push(l);
            if (r) queue.push(r);
        }
    return depth;
};

总结：

本题主要考察二叉树的各种遍历方式，要求熟练掌握，此外还应掌握递归的使用。