GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — 111. 二叉树的最小深度 · SinceraXY/Algorithm_code@be4375e

File tree

Expand file treeCollapse file tree
Open diff view settings
Filter options
  • leetcode/easy/111_二叉树的最小深度
    • 111_二叉树的最小深度.cpp
    • 111_二叉树的最小深度.go
    • 111_二叉树的最小深度.py
    • README.md
Expand file treeCollapse file tree
Open diff view settings
Collapse file

‎leetcode/easy/111_二叉树的最小深度/111_二叉树的最小深度.cpp‎

Copy file name to clipboard
+65Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* struct TreeNode {
4+
* int val;
5+
* TreeNode *left;
6+
* TreeNode *right;
7+
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
8+
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9+
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10+
* };
11+
*/
12+
13+
//递归法
14+
class Solution {
15+
public:
16+
int getDepth(TreeNode* node) {
17+
if(node==NULL) return 0;
18+
int leftDepth=getDepth(node->left);
19+
int rightDepth=getDepth(node->right);
20+
21+
if(node->left==NULL&&node->right!=NULL){
22+
return 1 + rightDepth;
23+
}
24+
if(node->left!=NULL&&node->right==NULL){
25+
return 1 + leftDepth;
26+
}
27+
int result= 1 + min(leftDepth,rightDepth);
28+
return result;
29+
}
30+
int minDepth(TreeNode* root) {
31+
return getDepth(root);
32+
}
33+
};
34+
35+
36+
37+
//迭代法
38+
class Solution {
39+
public:
40+
int minDepth(TreeNode* root) {
41+
if(root==NULL) return 0;
42+
int depth = 0;
43+
queue<TreeNode*> que;
44+
que.push(root);
45+
while(!que.empty()){
46+
int size=que.size();
47+
depth++;
48+
int flag=0;
49+
for(int i=0;i<size;i++)
50+
{
51+
TreeNode* node=que.front();
52+
que.pop();
53+
if(node->left) que.push(node->left);
54+
if(node->right) que.push(node->right);
55+
if(!node->left&&!node->right)
56+
{
57+
flag=1;
58+
break;
59+
}
60+
}
61+
if(flag==1) break;
62+
}
63+
return depth;
64+
}
65+
};
Collapse file

‎leetcode/easy/111_二叉树的最小深度/111_二叉树的最小深度.go‎

Copy file name to clipboard
+69Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* type TreeNode struct {
4+
* Val int
5+
* Left *TreeNode
6+
* Right *TreeNode
7+
* }
8+
*/
9+
10+
//递归法
11+
func getDepth(node *TreeNode) int {
12+
if node == nil {
13+
return 0
14+
}
15+
16+
leftDepth := getDepth(node.Left)
17+
rightDepth := getDepth(node.Right)
18+
19+
if node.Left == nil && node.Right != nil {
20+
return 1 + rightDepth
21+
}
22+
if node.Left != nil && node.Right == nil {
23+
return 1 + leftDepth
24+
}
25+
26+
if leftDepth < rightDepth {
27+
return 1 + leftDepth
28+
}
29+
return 1 + rightDepth
30+
}
31+
32+
func minDepth(root *TreeNode) int {
33+
return getDepth(root)
34+
}
35+
36+
37+
38+
//迭代法
39+
func minDepth(root *TreeNode) int {
40+
if root == nil {
41+
return 0
42+
}
43+
44+
depth := 0
45+
que := []*TreeNode{root}
46+
for len(que) > 0 {
47+
size := len(que)
48+
depth++
49+
flag := 0
50+
for i := 0; i < size; i++ {
51+
node := que[0]
52+
que = que[1:]
53+
if node.Left != nil {
54+
que = append(que, node.Left)
55+
}
56+
if node.Right != nil {
57+
que = append(que, node.Right)
58+
}
59+
if node.Left == nil && node.Right == nil {
60+
flag = 1
61+
break
62+
}
63+
}
64+
if flag == 1 {
65+
break
66+
}
67+
}
68+
return depth
69+
}
Collapse file

‎leetcode/easy/111_二叉树的最小深度/111_二叉树的最小深度.py‎

Copy file name to clipboard
+53Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
# Definition for a binary tree node.
2+
# class TreeNode:
3+
# def __init__(self, val=0, left=None, right=None):
4+
# self.val = val
5+
# self.left = left
6+
# self.right = right
7+
8+
#递归法
9+
class Solution:
10+
def getDepth(self, node: Optional[TreeNode]) -> int:
11+
if node is None:
12+
return 0
13+
14+
leftDepth = self.getDepth(node.left)
15+
rightDepth = self.getDepth(node.right)
16+
17+
if node.left is None and node.right is not None:
18+
return 1 + rightDepth
19+
if node.left is not None and node.right is None:
20+
return 1 + leftDepth
21+
22+
result = 1 + min(leftDepth, rightDepth)
23+
return result
24+
25+
def minDepth(self, root: Optional[TreeNode]) -> int:
26+
return self.getDepth(root)
27+
28+
29+
30+
#迭代法
31+
class Solution:
32+
def minDepth(self, root: Optional[TreeNode]) -> int:
33+
if root is None:
34+
return 0
35+
36+
depth = 0
37+
que = [root]
38+
while que:
39+
size = len(que)
40+
depth += 1
41+
flag = 0
42+
for _ in range(size):
43+
node = que.pop(0)
44+
if node.left:
45+
que.append(node.left)
46+
if node.right:
47+
que.append(node.right)
48+
if not node.left and not node.right:
49+
flag = 1
50+
break
51+
if flag == 1:
52+
break
53+
return depth
Collapse file

‎leetcode/easy/111_二叉树的最小深度/README.md‎

Copy file name to clipboard
+136Lines changed: 136 additions & 0 deletions
  • Display the source diff
  • Display the rich diff
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,136 @@
1+
# 111. 二叉树的最小深度
2+
3+
- **平台**：LeetCode
4+
- **链接**：https://leetcode.cn/problems/minimum-depth-of-binary-tree/
5+
- **难度**：Easy
6+
- **标签**：树、深度优先搜索、广度优先搜索、二叉树
7+
8+
## 题目描述
9+
10+
给定一个二叉树，找出其最小深度。
11+
12+
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
13+
14+
注意：叶子节点是指没有子节点的节点，也就是左右孩子都为空的节点。
15+
16+
## 示例
17+
18+
**示例 1：**
19+
20+
```text
21+
输入：root = [3,9,20,null,null,15,7]
22+
输出：2
23+
```
24+
25+
**示例 2：**
26+
27+
```text
28+
输入：root = [2,null,3,null,4,null,5,null,6]
29+
输出：5
30+
```
31+
32+
**示例 3：**
33+
34+
```text
35+
输入：root = []
36+
输出：0
37+
```
38+
39+
## 解题思路
40+
41+
本题和「104. 二叉树的最大深度」相似，但最小深度有一个重要区别：
42+
43+
如果某个节点只有一个子树为空，不能直接把空子树的深度 `0` 作为最小值。因为从根节点到空节点不是一条到叶子节点的路径。
44+
45+
例如：
46+
47+
```text
48+
1
49+
\
50+
2
51+
```
52+
53+
这棵树的最小深度是 `2`，不是 `1`。
54+
55+
### 方法一：递归法
56+
57+
#### 思路与算法
58+
59+
定义 `getDepth(node)` 表示以 `node` 为根节点的最小深度。
60+
61+
递归终止条件：
62+
63+
```text
64+
如果 node 为空，返回 0
65+
```
66+
67+
然后分别计算左右子树深度：
68+
69+
```text
70+
leftDepth = getDepth(node.left)
71+
rightDepth = getDepth(node.right)
72+
```
73+
74+
需要分情况讨论：
75+
76+
1. 左子树为空，右子树不为空：最小深度只能从右子树走，返回 `1 + rightDepth`；
77+
2. 左子树不为空，右子树为空：最小深度只能从左子树走，返回 `1 + leftDepth`；
78+
3. 左右子树都为空或都不为空：返回 `1 + min(leftDepth, rightDepth)`。
79+
80+
这里的关键是：只有左右孩子都为空的节点才是叶子节点。
81+
82+
### 方法二：迭代法（层序遍历）
83+
84+
#### 思路与算法
85+
86+
使用队列进行层序遍历。
87+
88+
因为层序遍历是从上到下一层一层访问，所以第一次遇到叶子节点时，当前层数就是二叉树的最小深度。
89+
90+
具体过程：
91+
92+
1. 如果根节点为空，返回 `0`；
93+
2. 将根节点入队，初始化 `depth = 0`；
94+
3. 每轮处理当前层所有节点，处理前 `depth += 1`；
95+
4. 如果当前节点没有左右孩子，说明找到最近叶子节点，直接结束遍历；
96+
5. 否则将非空左右孩子加入队列。
97+
98+
## 代码实现
99+
100+
### C++
101+
102+
详见 [111_二叉树的最小深度.cpp](./111_二叉树的最小深度.cpp)
103+
104+
当前 C++ 文件包含两种写法：
105+
106+
- 递归法；
107+
- 迭代法（层序遍历）。
108+
109+
### Python
110+
111+
详见 [111_二叉树的最小深度.py](./111_二叉树的最小深度.py)
112+
113+
### Go
114+
115+
详见 [111_二叉树的最小深度.go](./111_二叉树的最小深度.go)
116+
117+
## 复杂度分析
118+
119+
设二叉树节点数为 `n`，树高为 `h`。
120+
121+
### 递归法
122+
123+
- **时间复杂度**：`O(n)`，最坏情况下需要访问所有节点。
124+
- **空间复杂度**：`O(h)`，主要来自递归调用栈。平衡二叉树为 `O(log n)`，最坏情况下树退化成链表，为 `O(n)`。
125+
126+
### 迭代法（层序遍历）
127+
128+
- **时间复杂度**：`O(n)`，最坏情况下需要遍历所有节点。
129+
- **空间复杂度**：`O(n)`，最坏情况下队列中可能保存大量节点。
130+
131+
## 关键点
132+
133+
1. 空树的最小深度为 `0`。
134+
2. 叶子节点必须满足：左右孩子都为空。
135+
3. 递归法不能简单写成 `1 + min(leftDepth, rightDepth)`，否则会误用空子树深度。
136+
4. 层序遍历第一次遇到叶子节点时，当前深度就是答案。

0 commit comments

Comments
0 (0)
You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.