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

视频讲解：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)
    {
        //如果是空节点，返回0
        if(!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;
        //如果左右子树不存在，返回0
        if(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) {
        //初始化result
        result=0;
        //如果节点为空，返回result
        if(!root) return result;

        //节点不为空
        getDepth(root,1);
        return result;
    }
};

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

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