111. 二叉树的最小深度(Minimum Depth of Binary Tree) - 《leetcode》

来源
描述
题解
- 递归「深度优先搜索」
- 迭代「宽度优先搜索」

来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

描述

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。

示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最小深度 2.

题解

递归「深度优先搜索」

递归结束条件

当root节点左右孩子都为空时，返回1；
当root节点左右孩子有一个为空时，返回不为空的孩子节点的深度；

当root节点左右孩子都不为空时，返回左右孩子较小深度的节点值；

/**
* 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;
      // 叶子节点，直接返回1
      if (root.left == null && root.right == null) return 1;
      int m1 = minDepth(root.left);
      int m2 = minDepth(root.right);
      // 如果左孩子和右孩子其中一个为空，那么需要返回比较大的那个孩子的深度
      // 这里其中一个节点为空，说明m1和m2有一个必然为0，所以可以返回m1 + m2 + 1;
      if (root.left == null || root.right == null) return m1 + m2 + 1;
      // 左右孩子都不为空，返回最小深度+1
      return Math.min(m1, m2) + 1;
  }
}

当左右孩子均为空时，m1和m2均为0，也可以返回m1+m2+1，故精简代码：

/**
 * 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;
        int m1 = minDepth(root.left);
        int m2 = minDepth(root.right);
        //如果左孩子和右孩子存在空的情况，直接返回m1+m2+1;如果都不为空，返回较小深度+1
        return (root.left == null || root.right == null) ? (m1 + m2 + 1) : Math.min(m1, m2) + 1;
    }
}

复杂度分析

时间复杂度：我们访问每个节点一次，时间复杂度为，其中是节点个数。
空间复杂度：最坏情况下，整棵树是非平衡的，例如每个节点都只有一个孩子，递归会调用（树的高度）次，因此栈的空间开销是。但在最好情况下，树是完全平衡的，高度只有，因此在这种情况下空间复杂度只有。

迭代「宽度优先搜索」

广度优先搜索的性质保证了最先搜索到的叶子节点的深度一定最小

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    class QueueNode {
        TreeNode node;
        int depth;
        public QueueNode(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<QueueNode> queue = new LinkedList<>();
        queue.add(new QueueNode(root, 1));
        while (!queue.isEmpty()) {
            QueueNode queueNode = queue.poll();
            TreeNode node = queueNode.node;
            int depth = queueNode.depth;
            if (node.left == null && node.right == null) {
                return depth;
            }
            if (node.left != null) {
                queue.add(new QueueNode(node.left, depth + 1));
            }
            if (node.right != null) {
                queue.add(new QueueNode(node.right, depth + 1));
            }
        }
        return 0;
    }
}

复杂度分析

时间复杂度：，其中是树的节点数。对每个节点访问一次。
空间复杂度：，其中是树的节点数。空间复杂度主要取决于队列的开销，队列中的元素个数不会超过树的节点数。