递归训练一：Leetcode 104.二叉树的最大深度

题目描述

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

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

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

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

   3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

原题目链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree

题解

这里我需要说一下，做二叉树相关的题，你需要的最少技能是，

1、得知道啥是二叉树

2、掌握二叉树的前中后序遍历 + 层序遍历

如果这些都不懂的，我建议你先去学一学。

解法一：从上到下计算（前序遍历）

1、从根节点开始，每下降一层，就将深度+1

2、用全局变量来记录下最大深度

3、每当达到叶子节点时就与全局变量进行比较和更新

class Solution {
    // 全局变量，存放结果
    int res = 0;    
    public int maxDepth(TreeNode root) {
        // 深度遍历，一开始的深度为 0
        dfs(root, 0);    
        // 返回结果
        return this.res;     
    }

    public void dfs(TreeNode root, int length){
        // 如果到达叶子节点，就更新结果
        if (root == null){      
            // 选取最深的叶子节点作为结果
            res = Math.max(this.res, length);
            return;
        }
        // 由于当前节点有值，故深度要+1
        dfs(root.left, length+1);    // 查找左节点
        dfs(root.right, length+1);   // 查找右节点
    }
}

解法二：从下到上计算机（后序遍历）

1、若我们知道两个叶子节点的长度，那么我们就能通过两个叶子的最大深度再+1，得到根节点的最大深度。

2、而这种先知道两个子节点，再知道根节点恰好符合后序遍历的特点，具体看代码

class Solution {
    public int maxDepth(TreeNode root) {
        // 返回当前节点的最大深度
        return dfs(root);       
    }

    public int dfs(TreeNode root){
        // 如果是空节点，则深度为 0
        if (root == null){    
            return 0;
        }
        // 遍历左节点得到左节点的最大深度
        int leftLength = dfs(root.left);  
        // 遍历右节点得到右节点的最大深度
        int rightLength = dfs(root.right);   
        // 返回两个节点的最大深度，再加根节点的深度（+1）
        return Math.max(leftLength, rightLength) + 1;  
    }
}

解法三：层序遍历

1、使用队列来存放节点

2、一开始先知道当前层数的节点个数，然后根据个数出队，并对其孩子节点入队

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        // 创建一个队列
        Deque<TreeNode> deque = new LinkedList<>(); 
        // 根结点入队列，对应第一层
        deque.offer(root);                          
        int res = 0;
        // 如果队列不为空
        while (!deque.isEmpty()){
            // 层数
            res += 1;          
            // 找到当前层的节点数
            int length = deque.size();       
            // 清空当前层，并把孩子节点入队
            for (int i=0; i < length; i++){     
                TreeNode node = deque.pollFirst(); 
                if (node.left != null)
                    deque.offer(node.left);
                if (node.right != null)
                    deque.offer(node.right);
            }
        }
        return res;
    }
}

相关训练题

递归训练二：Leetcode 62.不同路径

递归训练三：剑指 Offer 16. 数值的整数次方

递归训练四：Leetcode 4. 寻找两个正序数组的中位数

帅地永久会员

打赏 收藏 海报挣佣金 推广链接