二叉树OJ题：LeetCode--104.二叉树的最大深度

1.题目介绍

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

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

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

2.实例演示

3.解题思路

要求二叉树的最大深度，我们同样的也是采用递归遍历的方法：

二叉树的最大深度等价于：左右子树的最大深度 + 1

要求1的高度，那么就得求它的左右子树2、3的高度，要求2和3的高度就得分别求它们左右子树的高度...依次类推，4的左右子树高度为0，这时4返回给2时返回的高度为0+1（0表示它的左右子树的高度为0，1表示它自己的高度为1），也就是说再返回时要加上自己本身的高度，所以2的左子树的高度为1，再来计算2的右子树5的高度，计算5的高度又得计算5的左右子树的高度，5的左子树高度为1，右子树高度为0，取较大的为1，5返回2时再加上自己本身的高度为2，所以取2的左右子树较高的高度为2，所以2返回1时再加上自己本身的高度为3.....依次类推，直到遍历完整个二叉树。所以最后整颗树的高度为4。

代码演示：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/*
解题思路：
二叉树的最大深度等价于：左右子树的最大深度 + 1
*/
int maxDepth(struct TreeNode* root){
    //为空树就返回0
    if(root == NULL)
        return 0;
    //计算左右子树的深度
    int High_Left = maxDepth(root->left) + 1; 
    int High_Right = maxDepth(root->right) + 1;
    //比较左右子树的大小，返回最大的深度
    if(High_Left > High_Right)
    {
        return High_Left;
    }
    return High_Right;
}

递归展开图：

每一次递归的返回值并不是直接返回到最外面，而是返回上一层，这一点要注意。

朋友们、伙计们，美好的时光总是短暂的，我们本期的的分享就到此结束，最后看完别忘了留下你们弥足珍贵的三连喔，感谢大家的支持！