瑞文考研算法每日一题—2023.06.01 二叉树的最大深度

Problem: 104. 二叉树的最大深度

方法一：递归

思路

由于树的定于具有递归性质，所以树的问题往往可以用递归解决。我们将原问题拆分更小规模的子问题，不断拆分后会有一个尽头，即递归边界条件。

• 子问题：设左子树的最大深度为$l$，右子树的最大深度为$r$。则当前结点最大深度为：$max(l,r)+1$
• 递归边界条件：当节点为空时

Code

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int maxDepth(TreeNode* root) {if(root == nullptr) return 0;return max(maxDepth(root->left), maxDepth(root->right)) + 1;}
};

复杂度

• 时间复杂度:
  $O(n)$，其中$n$为二叉树的节点个数。

• 空间复杂度:
  $O(n)$，当二叉树为链状时。