LeetCode刷题之路-104. 二叉树的最大深度

LeetCode刷题之路-104. 二叉树的最大深度

前言

求二叉树深度是一道非常经典的二叉树递归求解问题,它几乎出现在每本介绍二叉树的书籍中。如果能够明确递归问题的求解思路,很容易就做出来了。而且它的代码也极其简单,易于理解,现在让我们一起看一下这道题。

题目介绍

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

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

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

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

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

解题思路

  1. 首先明确递归的三大要素:

    • 第一要素:明确你这个函数想要干什么
    • 第二要素:寻找递归结束条件
    • 第三要素:找出函数的等价关系式

    来源于:https://www.iamshuaidi.com/272.html

  2. 按照上述步骤:

    • 我们递归函数的功能就是要求解以root为根的二叉树的最大深度,因此当前函数的参数只包含一个即root。一般递归函数中的参数就是变化的状态量。下面便是函数定义:

      int maxDepth(TreeNode root) {
          
      }
      
    • 递归结束条件很简单,当一层层往下走,走到底就是root == null时,二叉树的深度为0。加入递归结束条件,我们的代码变为:

      int maxDepth(TreeNode root) {
          if(root == null)
             	return 0;
      }
      
    • 最重要的步骤找出函数的等价关系式:root为根的二叉树深度会有两个子问题,即左子树的深度和右子树的深度。那么我们就需要通过这两个子问题的解来还原出原始问题的解,大家想一下,如果我们已经得到了左子树的最大深度和右子树的最大深度,那么以root为根的二叉树最大深度会是什么?是不是就是左右子树较大深度的那一个+1即可,因为左右子树是比当前树的层数少1的。因此等价关系式即为:max(左子树最大深度,右子树最大深度) + 1。那我们的代码变为:

      int maxDepth(TreeNode root) {
          if(root == null)
             	return 0;
          int leftDepth = maxDepth(root.left);
          int rightDepth = maxDepth(root.right);
          return Math.max(leftDepth, rightDepth) + 1;
      }
      

      精简一下:

      int maxDepth(TreeNode root) {
          if(root == null)
             	return 0;
          return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
      }
      

结语

这道题只要理解了递归方法的精髓,很容易就做出来了!但是它是二叉树递归问题的一道经典例题,很多问题都是由这道题延伸出来的。

再就是大家有没有发现它是三大遍历中的哪一种?(中序遍历,前序遍历,后序遍历),答案是后序遍历。先计算遍历左右子树,再遍历根节点。大家根据后序遍历的框架也能很容易就写出来了。

最后,希望此文章能给大家带来收获,谢谢大家!

上一篇:leetcode 二叉树的最大深度 简单


下一篇:LeetCode-104-二叉树的最大深度