LeetCode 104. 二叉树的最大深度-Js中文网

题目描述

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

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

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

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

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

难度：Middle

前置知识

递归

公司

阿里
腾讯
百度
字节
apple
linkedin
uber
yahoo

思路

由于树是一种递归的数据结构，因此用递归去解决的时候往往非常容易，这道题恰巧也是如此，
用递归实现的代码如下：

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));
};

如果使用迭代呢？我们首先应该想到的是树的各种遍历，由于我们求的是深度，因此
使用层次遍历（BFS）是非常合适的。我们只需要记录有多少层即可。相关思路请查看binary-tree-traversal

关键点解析

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

代码

语言支持：JS，C++，Java，Python

JavaScript Code:

/*
 * @lc app=leetcode id=104 lang=javascript
 *
 * [104] Maximum Depth of Binary Tree
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
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;
};

C++ Code:

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：是以前端进阶资源教程分享为主的专业网站，包括：前端、大厂面试题、typescript教程、程序人生、React.js
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        auto q = vector<TreeNode*>();
        auto d = 0;
        q.push_back(root);
        while (!q.empty())
        {
            ++d;
            auto sz = q.size();
            for (auto i = 0; i < sz; ++i)
            {
                auto t = q.front();
                q.erase(q.begin());
                if (t->left != nullptr) q.push_back(t->left);
                if (t->right != nullptr) q.push_back(t->right);
            }
        }
        return d;
    }
};

Java Code:

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：是以前端进阶资源教程分享为主的专业网站，包括：前端、大厂面试题、typescript教程、程序人生、React.js
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null)
        {
            return 0;
        }
        // 队列
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int res = 0;
        // 按层扩展
        while(!queue.isEmpty())
        {
            // 拿出该层所有节点，并压入子节点
            int size = queue.size();
            while(size > 0)
            {
                TreeNode node = queue.poll();

                if(node.left != null)
                {
                    queue.offer(node.left);
                }
                if(node.right != null)
                {
                    queue.offer(node.right);
                }
                size-=1;
            }
            // 统计层数
            res +=1;
        }
        return res;
    }
}

Python Code:

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        q, depth = [root, None], 1
        while q:
            node = q.pop(0)
            if node:
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
            elif q:
                q.append(None)
                depth += 1
        return depth

复杂度分析