美文网首页
leetcode--01.二叉树最小深度

leetcode--01.二叉树最小深度

作者: yui_blacks | 来源:发表于2018-11-12 22:48 被阅读0次

感觉一天一道剑指offer题不够,就再加上一天一道leetcode吧

题目:
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.
给定一棵二叉树,求出它的最小深度。最小深度是从根节点到最近的叶节点的最短路径上的节点数。

思路:
5种情况:空树;没有子树;只有左/右子树;有俩子树

本题要注意最小深度与最大深度的区别:对于最大深度,不需要考虑当前子树是否为单子树(即一侧子树深度为0)的情况,即最大深度一直等于左右子树的最大值;对于最小深度,需要考虑当前子树是否为单子树的情况,对于双子树,其最小深度为左右子树的最小值,对于单子树,其最小深度为左右深度的最大值(因为有一侧的子树为0)。

可采用层序遍历和深度优先遍历,这题的话层序遍历效率高一点,因为若是找到一个叶子节点那么肯定是最短的,无需遍历所有节点,贴的代码用的递归

二叉树操作主要还是利用尾递归或者循环遍历这两种思路,进而涉及DFS(主要利用递归或者栈实现)或者BFS(主要利用队列实现)。剩下的只需要按照这些思路即可。

public class Solution { 
    public int run(TreeNode root) { 
        if(root==null)
            return 0;
        if(root.left==null && root.right==null)
            return 1;
        if(root.left==null || root.right==null)
            return Math.max(run(root.left),run(root.right))+1;
        return Math.min(run(root.left),run(root.right))+1; 
    } 
}

相关文章

  • 111. Minimum Depth of Binary Tre

    题目 给定一个二叉树,求二叉树最小深度 解析 一个二叉树的最小深度,就是求左子树最小深度或者右子树最小深度,然后加...

  • leetcode--01.二叉树最小深度

    感觉一天一道剑指offer题不够,就再加上一天一道leetcode吧 题目:Given a binary tree...

  • 二叉树面试题基本问题

    二叉树的最大深度与最小深度 二叉树的最大深度 最大深度是指二叉树根节点到该树叶子节点的最大路径长度。而最小深度自然...

  • Swift - LeetCode - 二叉树的最小深度

    题目 二叉树的最小深度 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。...

  • Leetcode 111 二叉树的最小深度

    二叉树的最小深度 题目 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。...

  • 111.二叉树的最小深度

    题目#111.二叉树的最小深度 给定一个二叉树,找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点...

  • LeetCode 111. 二叉树的最小深度(Minimum D

    111. 二叉树的最小深度 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数...

  • [LeetCode]111. 二叉树的最小深度

    111. 二叉树的最小深度给定一个二叉树,找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。...

  • 111. 二叉树的最小深度

    111. 二叉树的最小深度 给定一个二叉树,找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量...

  • 111. 二叉树的最小深度(Python)

    题目 难度:★★☆☆☆类型:二叉树 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上...

网友评论

      本文标题:leetcode--01.二叉树最小深度

      本文链接:https://www.haomeiwen.com/subject/gvshfqtx.html