当前位置：首页 > news >正文

【代码随想录day 14】力扣 104.二叉树的最大深度

news 2025/8/9 14:01:39

视频讲解：https://www.bilibili.com/video/BV1Gd4y1V75u/?vd_source=a935eaede74a204ec74fd041b917810c
文档讲解：https://programmercarl.com/0104.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6.html
力扣题目：https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/

这道题还是使用递归的办法，前序遍历和后序遍历都可以实现，先讲一下后序遍历的代码，主要流程就是不断向下摸索去找，然后深度就等于1+左子树的深度和右子树深度的最大值，需要注意的是，判断节点为空的语句不能再主函数，因为每次调用getDepth函数都要去判断节点是否为空。

class Solution {
public:
//后序遍历int getDepth(TreeNode *node){//如果是空节点，返回0if(!node){return 0;}int left=getDepth(node->left);int right=getDepth(node->right);int depth=1+max(left,right);return depth;}int maxDepth(TreeNode *root){int result= getDepth(root);return result;}

接下来再来讲前序遍历，前序遍历比较符合我们的思路去从上而下找到子树的最大深度，往下走就depth++，找到头之后就要回溯到原来分叉的节点，所以depth–，知道函数结束，depth的值就是子树的最大深度。

//前序遍历，容易理解
class Solution {
public:int result;void getDepth(TreeNode *node, int depth){result= depth>result ? depth: result;//如果左右子树不存在，返回0if(node->left==NULL &&node->right==NULL){return;}if(node->left){depth++;getDepth(node->left,depth);//回溯depth--;}if(node->right){depth++;getDepth(node->right,depth);//回溯depth--;}return;}int maxDepth(TreeNode* root) {//初始化resultresult=0;//如果节点为空，返回resultif(!root) return result;//节点不为空getDepth(root,1);return result;}
};

同时附上C代码，与后序遍历思想类似，直接递归到叶子节点，求深度的最大值+1.

int maxDepth(struct TreeNode* root) {//如果节点不存在，直接等于0if(!root){return 0;}//节点存在，递归左节点和右节点int left= maxDepth(root->left);int right=maxDepth(root->right);int max =left>right ? left :right;return max+1;
}