二叉树的最小深度

发表于
本文字数： 705 阅读时长 ≈ 1 分钟

LeetCode每日一题，111. Minimum Depth of Binary Tree

先看题目描述

大意就是求二叉树的最小深度，即是叶子节点到根节点的最小距离

算法思路

这题很简单，用递归就可以解决，理解好递归结束条件即可

  • 当 root 为空时返回 0
  • 当 root 的左右子树有一个为空时，返回非空子树的最小深度 + 1
  • 上面两个条件都不满足时，返回左右子树的最小深度 + 1

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null) return minDepth(root.right) + 1;
        if (root.right == null) return minDepth(root.left) + 1;
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}