二叉树的最小深度

一、需求

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

• 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

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

输入：root = [3,9,20,null,null,15,7]输出：2

二、BFS法

2.1  思路分析

1. 该思路根据求二叉树的最大深度：https://blog.csdn.net/Sruggle/article/details/110429246而来；
2. 利用队列保存二叉树的每一行，一行一行的进行；

2.2  代码实现

class Solution {    public int minDepth(TreeNode root) {        if(root == null) return 0;        List<TreeNode> queue = new LinkedList<>();        queue.add(root);        int res = 0;        while(queue.size() != 0) {            res  ;            List<TreeNode> tmp = new LinkedList<>();            for(TreeNode node : queue) {                if(node.left == null && node.right == null) return res;                if(node.left != null) tmp.add(node.left);                if(node.right != null) tmp.add(node.right);            }            queue = tmp;        }        return res;            }}

2.3  复杂度分析

• 时间复杂度为O(N)，最坏情况下，二叉树为满二叉树时，需要遍历所有的节点；
• 空间复杂度为O(N)，最坏情况下，二叉树为满二叉树时，队列需要同时存储N/2的节点；

三、DFS法

3.1  思路分析

1. 思路与求二叉树的最大深度类似，多加了两个判断，用来排除左子树或右子树为空的情况；

3.2  代码实现

class Solution {    public int minDepth(TreeNode root) {        if(root == null) return 0;        //左、右子树深度        int left = minDepth(root.left);        int right = minDepth(root.right);        //左(右)子树为空，深度为右(左)子树深度 当前节点深度1        if(left == 0) return right   1;        if(right == 0) return left   1;        //左、右子树不为空，深度为左、右子树深度较小者 当前节点深度1        return Math.min(left, right)   1;    }}

3.3  复杂度分析

• 时间复杂度为O(N)，递归需要遍历二叉树的所有节点；
• 空间复杂度为O(N)，递归的深度最多可达N；

来源：https://www.icode9.com/content-4-837951.html