leetcode：104. 二叉树的最大深度

题目

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

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

  1.     3
  2.    / \
  3.   9  20
  4.     /  \
  5.    15   7

返回它的最大深度 3 。

解答 & 代码

二叉树题目的递归（DFS）解法可以分两类思路：

  1. 解法一：遍历一遍二叉树得出答案：对应着 回溯算法核心框架

  2. 解法二：通过分解问题计算出答案：对应着 动态规划核心框架。

    解法一：递归遍历（回溯）

    1. /**
    2. * Definition for a binary tree node.
    3. * struct TreeNode {
    4. *     int val;
    5. *     TreeNode *left;
    6. *     TreeNode *right;
    7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10. * };
    11. */
    12. class Solution {
    13. private:
    14.  int cur_depth = 0;    // 当前节点的深度
    15.  int max_depth = 0;    // 二叉树的最大深度
    17.  // 递归遍历二叉树（深度优先搜索）
    18.  void dfs(TreeNode* root)
    19.  {
    20.      // 递归结束条件：到达 nullptr，更新最大深度
    21.      if(root == nullptr)
    22.      {
    23.          max_depth = max(max_depth, cur_depth);
    24.          return;
    25.      }
    27.      // 前序位置（代表进入当前节点），更新当前节点深度（深度 +1）
    28.      ++cur_depth;
    29.      // 递归处理左右子树
    30.      dfs(root->left);
    31.      dfs(root->right);
    32.      // 后序位置（代表离开当前节点），节点深度 -1
    33.      --cur_depth;
    34.  }
    35. public:
    36.  int maxDepth(TreeNode* root) {
    37.      dfs(root);
    38.      return max_depth;
    39.  }
    40. };

    复杂度分析：设二叉树共 N 个节点

  • 时间复杂度 O(N)：遍历每个节点一次
  • 空间复杂度 O(log N)：栈空间取决于递归深度，即二叉树的高度

执行结果：

  1. 执行结果：通过
  3. 执行用时：8 ms, 在所有 C++ 提交中击败了 62.84% 的用户
  4. 内存消耗：18.5 MB, 在所有 C++ 提交中击败了 23.56% 的用户

解法二：递归分解（动态规划）

后序遍历：先递归得到左子树的最大深度和右子树的最大深度，然后计算当前这棵树的最大深度

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int maxDepth(TreeNode* root) {
  15.         // 递归结束条件：当前节点为 nullptr，返回深度 0
  16.         if(root == nullptr)
  17.             return 0;
  18.         // 先递归得到左子树的最大深度和右子树的最大深度
  19.         int left_max_depth = maxDepth(root->left);
  20.         int right_max_depth = maxDepth(root->right);
  21.         // 后序位置，得到当前这棵树的深度（左右子树深度最大值 + 当前节点自己），并返回
  22.         return 1 + max(left_max_depth, right_max_depth);
  23.     }
  24. };

复杂度分析：设二叉树共 N 个节点

  • 时间复杂度 O(N)：遍历每个节点一次
  • 空间复杂度 O(log N)：栈空间取决于递归深度，即二叉树的高度

执行结果：

  1. 执行结果：通过
  3. 执行用时：4 ms, 在所有 C++ 提交中击败了 91.71% 的用户
  4. 内存消耗：18.3 MB, 在所有 C++ 提交中击败了 87.70% 的用户