首页 > 其他分享 >[Leetcode] 0111. 二叉树的最小深度

[Leetcode] 0111. 二叉树的最小深度

时间:2023-10-31 15:04:00浏览次数:44  
标签:node 0111 TreeNode right 二叉树 return root Leetcode left

111. 二叉树的最小深度

题目描述

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

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

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

 

示例 1:

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

示例 2:

输入:root = [2,null,3,null,4,null,5,null,6]
输出:5

 

提示:

  • 树中节点数的范围在 [0, 105]
  • -1000 <= Node.val <= 1000

解法

方法一:递归

递归的终止条件是当前节点为空,此时返回 \(0\);如果当前节点左右子树有一个为空,返回不为空的子树的最小深度加 \(1\);如果当前节点左右子树都不为空,返回左右子树最小深度的较小值加 \(1\)。

时间复杂度 \(O(n)\),空间复杂度 \(O(n)\)。其中 \(n\) 是二叉树的节点个数。

方法二:BFS

使用队列实现广度优先搜索,当我们找到一个叶子节点时,直接返回这个叶子节点的深度。广度优先搜索的性质保证了最先搜索到的叶子节点的深度一定最小。

时间复杂度 \(O(n)\),空间复杂度 \(O(n)\)。其中 \(n\) 是二叉树的节点个数。

Python3

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        if root.left is None:
            return 1 + self.minDepth(root.right)
        if root.right is None:
            return 1 + self.minDepth(root.left)
        return 1 + min(self.minDepth(root.left), self.minDepth(root.right))
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0

        que = collections.deque([(root, 1)])
        while que:
            node, depth = que.popleft()
            if not node.left and not node.right:
                return depth
            if node.left:
                que.append((node.left, depth + 1))
            if node.right:
                que.append((node.right, depth + 1))
        
        return 0

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) {
            return 0;
        }
        if (!root->left) {
            return 1 + minDepth(root->right);
        }
        if (!root->right) {
            return 1 + minDepth(root->left);
        }
        return 1 + min(minDepth(root->left), minDepth(root->right));
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode *root) {
        if (root == nullptr) {
            return 0;
        }

        queue<pair<TreeNode *, int> > que;
        que.emplace(root, 1);
        while (!que.empty()) {
            TreeNode *node = que.front().first;
            int depth = que.front().second;
            que.pop();
            if (node->left == nullptr && node->right == nullptr) {
                return depth;
            }
            if (node->left != nullptr) {
                que.emplace(node->left, depth + 1);
            }
            if (node->right != nullptr) {
                que.emplace(node->right, depth + 1);
            }
        }

        return 0;
    }
};

标签:node,0111,TreeNode,right,二叉树,return,root,Leetcode,left
From: https://www.cnblogs.com/yege/p/17800213.html

相关文章

  • 【NO.98】LeetCode HOT 100—621. 任务调度器
    题目:621.任务调度器给你一个用字符数组tasks表示的CPU需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行,并且每个任务都可以在1个单位时间内执行完。在任何一个单位时间,CPU可以完成一个任务,或者处于待命状态。然而,两个相同种类的任务之间......
  • 【NO.99】LeetCode HOT 100—647. 回文子串
    题目:647.回文子串给你一个字符串s,请你统计并返回这个字符串中回文子串的数目。回文字符串是正着读和倒过来读一样的字符串。子字符串是字符串中的由连续字符组成的一个序列。具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。示例1:输入:s=“......
  • 【NO.100】LeetCode HOT 100—739. 每日温度
    题目:739.每日温度给定一个整数数组temperatures,表示每天的温度,返回一个数组answer,其中answer[i]是指对于第i天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用0来代替。示例1:输入:temperatures=[73,74,75,71,69,72,76,73]输出:[1,1,4,2,1,1......
  • 代码随想录训练营第二十天打卡(Python)| 654.最大二叉树 、617.合并二叉树 、700.二叉搜
    654.最大二叉树1、使用切片classSolution:defconstructMaximumBinaryTree(self,nums:List[int])->Optional[TreeNode]:iflen(nums)==0:returnNonemax_val=max(nums)max_index=nums.index(max_val)node=T......
  • LeetCode232.用栈实现队列
    题目描述请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):实现MyQueue类:voidpush(intx)将元素x推到队列的末尾intpop()从队列的开头移除并返回元素intpeek()返回队列开头的元素booleanempty()如果队列为空,返回tr......
  • 代码随性训练营第十七天(Python)| 110.平衡二叉树、257. 二叉树的所有路径、404.左叶子之
    110.平衡二叉树1、递归法classSolution:defisBalanced(self,root:Optional[TreeNode])->bool:ifself.get_height(root)!=-1:#-1代表高度差大于1returnTrueelse:returnFalsedefget_height(self,root):......
  • 二叉树概念和操作
    二叉树定义二叉树(BinaryTree)是n(n>=0)个结点所构成的集合,它或为空树(n=0);或为非空树,对于非空树$T$:有且仅有一个称之为根的结点除根节点以外的其余结点分为两个互不相交的子集$T_1$和$T_2$,分别称为$T$的左子树和右子树,且$T_1$和$T_2$本身又是二叉树二叉树性质及存储结构通过......
  • [Leetcode] 0832. 翻转图像
    832.翻转图像题目描述给定一个 nxn 的二进制矩阵 image ,先水平翻转图像,然后 反转 图像并返回 结果 。水平翻转图片就是将图片的每一行都进行翻转,即逆序。例如,水平翻转 [1,1,0] 的结果是 [0,1,1]。反转图片的意思是图片中的 0 全部被 1 替换, 1 全部被......
  • 平衡二叉树AVL
    在计算机科学中,AVL树是最早被发明的自平衡二叉查找树。在AVL树中,任一节点对应的两棵子树的最大高度差为1,因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是$O(logn)$。所以我们可知,AVL树首先是二叉查找树(BST),不了解BST的同学可以了解一下,因为AVL树......
  • [Leetcode] 0830. 较大分组的位置
    830.较大分组的位置题目描述在一个由小写字母构成的字符串s中,包含由一些连续的相同字符所构成的分组。例如,在字符串s="abbxxxxzyy" 中,就含有"a","bb","xxxx","z"和"yy"这样的一些分组。分组可以用区间[start,end]表示,其中start和end分别表示该分组的起始......