我要招人

去企业版

首页 > 试题广场 >

二叉树的最小深度

[编程题]二叉树的最小深度

热度指数：4152 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一颗节点数为N的二叉树，求其最小深度。最小深度是指树的根节点到最近叶子节点的最短路径上节点的数量。

（注：叶子节点是指没有子节点的节点。）

数据范围：

0<=N<=6000

0<=val<=100

你能使用时间复杂度为O(N)，空间复杂度为O(logN)的解法通过本题吗？

例如当输入{1,2,3,4,5}时，对应的二叉树如下图所示：

可以看出离根节点最近的叶子节点是节点值为3的节点，所以对应的输出为2。

示例1

输入

{1,2,3,4,5}

输出

示例2

输入

{1,#,2,#,3}

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

牛客768685351号

发表于 2022-03-13 12:09:18

解决思路类似于“寻找最近公共祖先”，采用后序遍历的思路 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), lef 展开全文

lan爱学习

发表于 2022-03-04 20:40:55

class Solution { public: int search(TreeNode* node){ if(!node) return NULL; int temp=1; if(!node-& 展开全文

Kuris

发表于 2022-08-06 10:09:01

BFS import java.util.*; public class Solution { public int run (TreeNode root) { if(root == null){ return 0; } 展开全文

小小小明哥

发表于 2022-01-19 17:30:04

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) { 展开全文

觅杳

发表于 2023-01-09 17:46:04

考虑类似于最大深度的求法，即使用递归。到达叶子节点，即左右节点都为null，返回 0(较小的深度，但两边都是0) + 1；节点的左右子树都不为null，返回左右子树较小的深度 + 1；节点的左右子树只有一方为null时，求法有所不同，要返回的应该是左右子树深度较大的 + 1，而不是较小的。(因为当节展开全文

奇点nlp

发表于 2022-05-24 17:47:46

思路：使用层次遍历的思想当节点左右孩子都是空返回当前层 # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solutio 展开全文

T、MAN

发表于 2023-05-07 11:13:03

import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int v 展开全文

fred-coder

发表于 2021-12-07 01:32:34

根据二叉树的特点，前序遍历整棵树，遇到叶子节点记录整条路径上的节点数;用一个全局变量记录整棵树的最小深度,注意判空 # class TreeNode: # def __init__(self, x): # self.val = x # self.left = 展开全文

姐姐的遮阳伞

发表于 2022-03-27 21:21:32

import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int v 展开全文

已注销

发表于 2024-07-09 22:31:23

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) { 展开全文