C++实现LeetCode(111.二叉树的最小深度)

2024-10-31 16:18:52

[LeetCode] 111. 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.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7

return its minimum depth = 2.

二叉树的经典问题之最小深度问题就是就最短路径的节点个数，还是用深度优先搜索 DFS 来完成，万能的递归啊。首先判空，若当前结点不存在，直接返回0。然后看若左子结点不存在，那么对右子结点调用递归函数，并加1返回。反之，若右子结点不存在，那么对左子结点调用递归函数，并加1返回。若左右子结点都存在，则分别对左右子结点调用递归函数，将二者中的较小值加1返回即可，参见代码如下：

解法一：

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));
    }
};

我们也可以是迭代来做，层序遍历，记录遍历的层数，一旦遍历到第一个叶结点，就将当前层数返回，即为二叉树的最小深度，参见代码如下：

解法二：

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        int res = 0;
        queue<TreeNode*> q{{root}};
        while (!q.empty()) {
            ++res;
            for (int i = q.size(); i > 0; --i) {
                auto t = q.front(); q.pop();
                if (!t->left && !t->right) return res;
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
        }
        return -1;
    }
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/111

类似题目：

Binary Tree Level Order Traversal

Maximum Depth of Binary Tree

参考资料：

https://leetcode.com/problems/minimum-depth-of-binary-tree/

https://leetcode.com/problems/minimum-depth-of-binary-tree/discuss/36153/My-concise-c%2B%2B-solution

https://leetcode.com/problems/minimum-depth-of-binary-tree/discuss/36071/BFS-C%2B%2B-8ms-Beats-99.94-submissions

到此这篇关于C++实现LeetCode(111.二叉树的最小深度)的文章就介绍到这了,更多相关C++实现二叉树的最小深度内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

C++实现LeetCode(142.单链表中的环之二)

[LeetCode] 142. Linked List Cycle II 单链表中的环之二 Given a linked list, return the node where the cycle begins. If there is no cycle, return null. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexe
C++实现LeetCode(889.由先序和后序遍历建立二叉树)

[LeetCode] 889. Construct Binary Tree from Preorder and Postorder Traversal 由先序和后序遍历建立二叉树 Return any binary tree that matches the given preorder and postorder traversals. Values in the traversals pre and post are distinct positive integers. Example 1
C++实现LeetCode(141.单链表中的环)

[LeetCode] 141. Linked List Cycle 单链表中的环 Given a linked list, determine if it has a cycle in it. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to.
C++实现LeetCode(106.由中序和后序遍历建立二叉树)

[LeetCode] 106. Construct Binary Tree from Inorder and Postorder Traversal 由中序和后序遍历建立二叉树 Given inorder and postorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. For example, given ino
C++实现LeetCode(143.链表重排序)

[LeetCode] 143.Reorder List 链表重排序 Given a singly linked list L: L0→L1→-→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→- You may not modify the values in the list's nodes, only nodes itself may be changed. Example 1: Given 1->2->3->4, reorder it t
C++实现LeetCode(108.将有序数组转为二叉搜索树)

[LeetCode] 108.Convert Sorted Array to Binary Search Tree 将有序数组转为二叉搜索树 Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in wh
C++实现LeetCode(109.将有序链表转为二叉搜索树)

[LeetCode] 109.Convert Sorted List to Binary Search Tree 将有序链表转为二叉搜索树 Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary
C++实现LeetCode(104.二叉树的最大深度)

[LeetCode] 104. Maximum Depth of Binary Tree 二叉树的最大深度 Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Note: A leaf is a node with no child
C++实现LeetCode(111.二叉树的最小深度)

[LeetCode] 111. 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. Note: A leaf is a node with no child
Python实现二叉树的最小深度的两种方法

找到给定二叉树的最小深度最小深度是从根节点到最近叶子节点的最短路径上的节点数量注意:叶子节点没有子树 Example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its minimum depth = 2. 1:算法遍历二叉树每一层,一旦发现某层的某个结点无子树,就返回该层的深度,这个深度就是该二叉树的最小深度 def minDepth(self, root):
go语言算法题解二叉树的最小深度

目录题目: 说明: 解法: 题目: 给定一个二叉树,找出其最小深度. 最小深度是从根节点到最近叶子节点的最短路径上的节点数量. 说明: 叶子节点是指没有子节点的节点. 解法: func minDepth(root *TreeNode) int { if root == nil { return 0 } minDepth := math.MaxInt64 var dfs func(node *TreeNode, depth int) dfs = func(node *TreeNode, dept
C++实现LeetCode(103.二叉树的之字形层序遍历)

[LeetCode] 103. Binary Tree Zigzag Level Order Traversal 二叉树的之字形层序遍历 Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example
C++实现LeetCode(107.二叉树层序遍历之二)

[LeetCode] 107. Binary Tree Level Order Traversal II 二叉树层序遍历之二 Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root). Example 1: Input: root = [3
C++实现LeetCode(144.二叉树的先序遍历)

[LeetCode] 144. Binary Tree Preorder Traversal 二叉树的先序遍历 Given a binary tree, return the preorder traversal of its nodes' values. Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,2,3] Follow up: Recursive solution is trivial, could you do it iterat
C++实现LeetCode(94.二叉树的中序遍历)

[LeetCode] 94. Binary Tree Inorder Traversal 二叉树的中序遍历 Given a binary tree, return the inorder traversal of its nodes' values. Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] Follow up: Recursive solution is trivial, could you do it iteratively
C++实现LeetCode(112.二叉树的路径和)

[LeetCode] 112. Path Sum 二叉树的路径和 Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Note: A leaf is a node with no children. Example: Given the below bi
C++实现LeetCode(113.二叉树路径之和之二)

[LeetCode] 113. Path Sum II 二叉树路径之和之二 Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. For example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7

C++实现LeetCode(111.二叉树的最小深度)

[LeetCode] 111. Minimum Depth of Binary Tree 二叉树的最小深度

相关推荐

随机推荐