题目描述

链接: https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/submissions/

解题思路:

利用递归的思想, 分四种情况:

  • 当前节点空, 返回0
  • 当前节点的左节点飞空, 递归求左子树的最小深度, 返回+1(本身也算一个)
  • 当前节点的右节点飞空, 递归求右子树的最小深度, 返回+1(本身也算一个)
  • 左右节点都空, 返回1

代码:

// T: O(n), S: O(n)
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        if ((root.left == null) && (root.right == null)) return 1;
        int min_depth = Integer.MAX_VALUE;
        if (root.left != null) {
            min_depth = Math.min(minDepth(root.left), min_depth);
        }
        if (root.right != null) {
            min_depth = Math.min(minDepth(root.right), min_depth);
        }
        return min_depth + 1;
    }
}