Minimum Depth of Binary Tree

发布时间：2020-12-14 04:39:25 所属栏目：大数据来源：网络整理

导读：Question leetcode: Minimum Depth of Binary Tree | LeetCode OJ lintcode: (155) Minimum Depth of Binary Tree 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Given a binary tree,find its minimum depth. The minimum depth is the number of nodes al

Question

leetcode: Minimum Depth of Binary Tree | LeetCode OJ
lintcode: (155) Minimum Depth of Binary Tree

 
     Given a binary tree,find its minimum depth.

The minimum depth is the number of nodes along the shortest path
from the root node down to the nearest leaf node.

Example
Given a binary tree as follow:

        1

     /     

   2       3

          /    

        4      5
The minimum depth is 2

题解

注意审题，题中的最小深度指的是从根节点到最近的叶子节点（因为题中的最小深度是the number of nodes，故该叶子节点不能是空节点），所以需要单独处理叶子节点为空的情况。此题使用 DFS 递归实现比较简单。

Java

 
 
 
     /**
 * Definition of TreeNode: 大专栏 ?Minimum Depth of Binary Tree
 * public class TreeNode {
 * public int val;
 * public TreeNode left,right;
 * public TreeNode(int val) {
 * this.val = val;
 * this.left = this.right = null;
 * }
 * }
 */
public class Solution {
    /**
 * @param root: The root of binary tree.
 * @return: An integer.
 */
    public int minDepth(TreeNode root) {
        if (root == null) return 0;

        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);

        // current node is not leaf node
        if (root.left == null) {
            return 1 + rightDepth;
        } else if (root.right == null) {
            return 1 + leftDepth;
        }

        return 1 + Math.min(leftDepth,rightDepth);
    }
}
 
    

源码分析

建立好递归模型即可，左右子节点为空时需要单独处理下。

复杂度分析

每个节点遍历一次，时间复杂度 $$O(n)$$. 不计栈空间的话空间复杂度 $$O(1)$$.

Minimum Depth of Binary Tree

Question

题解

Java

源码分析

复杂度分析

推荐文章