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 — 二叉树层序遍历 · SinceraXY/Algorithm_code@4261518

File tree

Expand file treeCollapse file tree
Open diff view settings
Filter options
  • leetcode
    • easy/637_二叉树的层平均值
      • 637_二叉树的层平均值.cpp
      • 637_二叉树的层平均值.go
      • 637_二叉树的层平均值.py
      • README.md
    • medium
      • 199_二叉树的右视图
        • 199_二叉树的右视图.cpp
        • 199_二叉树的右视图.go
        • 199_二叉树的右视图.py
        • README.md
      • 429_N 叉树的层序遍历
        • 429_N 叉树的层序遍历.cpp
        • 429_N 叉树的层序遍历.go
        • 429_N 叉树的层序遍历.py
        • README.md
Expand file treeCollapse file tree
Open diff view settings
Collapse file

‎leetcode/easy/637_二叉树的层平均值/637_二叉树的层平均值.cpp‎

Copy file name to clipboard
+33Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
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+
class Solution {
13+
public:
14+
vector<double> averageOfLevels(TreeNode* root) {
15+
queue<TreeNode*> que;
16+
if(root!=NULL) que.push(root);
17+
vector<double>result;
18+
while(!que.empty()) {
19+
int size = que.size();
20+
double sum = 0; //统计每一层的和
21+
for(int i =0; i<size; i++)
22+
{
23+
TreeNode* node = que.front();
24+
que.pop();
25+
sum+=node->val;
26+
if(node->left) que.push(node->left);
27+
if(node->right) que.push(node->right);
28+
}
29+
result.push_back(sum/size); //将每一层均值放进结果集
30+
}
31+
return result;
32+
}
33+
};
Collapse file

‎leetcode/easy/637_二叉树的层平均值/637_二叉树的层平均值.go‎

Copy file name to clipboard
+28Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* type TreeNode struct {
4+
* Val int
5+
* Left *TreeNode
6+
* Right *TreeNode
7+
* }
8+
*/
9+
func averageOfLevels(root *TreeNode) []float64 {
10+
averages := []float64{}
11+
nextLevel := []*TreeNode{root}
12+
for len(nextLevel)>0 {
13+
sum := 0
14+
curLevel := nextLevel
15+
nextLevel = nil
16+
for _, node := range curLevel {
17+
sum += node.Val
18+
if node.Left != nil {
19+
nextLevel =append(nextLevel, node.Left)
20+
}
21+
if node.Right != nil {
22+
nextLevel = append(nextLevel, node.Right)
23+
}
24+
}
25+
averages = append(averages, float64(sum)/float64(len(curLevel)))
26+
}
27+
return averages
28+
}
Collapse file

‎leetcode/easy/637_二叉树的层平均值/637_二叉树的层平均值.py‎

Copy file name to clipboard
+23Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
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+
class Solution:
8+
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
9+
averages = list()
10+
queue = collections.deque([root])
11+
while queue:
12+
total = 0
13+
size = len(queue)
14+
for _ in range(size):
15+
node = queue.popleft()
16+
total += node.val
17+
left, right = node.left, node.right
18+
if left:
19+
queue.append(left)
20+
if right:
21+
queue.append(right)
22+
averages.append(total/size)
23+
return averages
Collapse file

‎leetcode/easy/637_二叉树的层平均值/README.md‎

Copy file name to clipboard
+89Lines changed: 89 additions & 0 deletions
  • Display the source diff
  • Display the rich diff
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
# 637. 二叉树的层平均值
2+
3+
- **平台**：LeetCode
4+
- **链接**：https://leetcode.cn/problems/average-of-levels-in-binary-tree/description/
5+
- **难度**：Easy
6+
- **标签**：树、深度优先搜索、广度优先搜索、二叉树
7+
8+
## 题目描述
9+
10+
给定一个非空二叉树的根节点 `root`，以数组的形式返回每一层节点值的平均值。与实际答案相差 `10^-5` 以内的结果可以被接受。
11+
12+
## 示例
13+
14+
**示例 1：**
15+
```
16+
输入：root = [3,9,20,null,null,15,7]
17+
输出：[3.00000,14.50000,11.00000]
18+
解释：第 0 层平均值为 3，第 1 层平均值为 (9+20)/2 = 14.5，第 2 层平均值为 (15+7)/2 = 11。
19+
```
20+
21+
**示例 2：**
22+
```
23+
输入：root = [3,9,20,15,7]
24+
输出：[3.00000,14.50000,11.00000]
25+
```
26+
27+
## 解题思路
28+
29+
### 方法一：迭代（广度优先搜索 BFS）
30+
31+
#### 思路与算法
32+
33+
按层遍历二叉树，每层统计其节点值之和与节点个数，即可得到该层的平均值。
34+
35+
1. 使用队列进行层序遍历。
36+
2. 每次循环前记录当前队列长度 `size`（当前层节点数）。
37+
3. 弹出 `size` 个节点：累加它们的值 `sum`，并将其左右孩子入队。
38+
4. 本层遍历结束后，将 `sum / size` 加入答案。
39+
40+
## 代码实现
41+
42+
### C++
43+
44+
```cpp
45+
class Solution {
46+
public:
47+
vector<double> averageOfLevels(TreeNode* root) {
48+
queue<TreeNode*> que;
49+
if(root!=NULL) que.push(root);
50+
vector<double>result;
51+
while(!que.empty()) {
52+
int size = que.size();
53+
double sum = 0; //统计每一层的和
54+
for(int i =0; i<size; i++)
55+
{
56+
TreeNode* node = que.front();
57+
que.pop();
58+
sum+=node->val;
59+
if(node->left) que.push(node->left);
60+
if(node->right) que.push(node->right);
61+
}
62+
result.push_back(sum/size); //将每一层均值放进结果集
63+
}
64+
return result;
65+
}
66+
};
67+
```
68+
69+
### Python
70+
71+
详见 [637_二叉树的层平均值.py](./637_二叉树的层平均值.py)
72+
73+
### Go
74+
75+
详见 [637_二叉树的层平均值.go](./637_二叉树的层平均值.go)
76+
77+
## 复杂度分析
78+
79+
时间复杂度：O(n)，其中 n 是二叉树中的节点个数。
80+
广度优先搜索需要对每个节点访问一次，时间复杂度是 O(n)。
81+
需要对二叉树的每一层计算平均值，时间复杂度是 O(h)，其中 h 是二叉树的高度，任何情况下都满足 h≤n。
82+
因此总时间复杂度是 O(n)。
83+
84+
空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度取决于队列开销，队列中的节点个数不会超过 n。
85+
86+
## 关键点
87+
88+
1. 分层遍历时必须先保存固定的 `size`，用来界定当前层的节点范围。
89+
2. `sum` 使用 `double`（或在 Python 中使用 `float`）避免整除与精度问题。
Collapse file

‎leetcode/medium/199_二叉树的右视图/199_二叉树的右视图.cpp‎

Copy file name to clipboard
+31Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
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+
class Solution {
13+
public:
14+
vector<int> rightSideView(TreeNode* root) {
15+
queue<TreeNode*>que;
16+
if(root!=NULL) que.push(root);
17+
vector<int> result;
18+
while(!que.empty()){
19+
int size=que.size();
20+
for(int i=0;i<size;i++)
21+
{
22+
TreeNode*node=que.front();
23+
que.pop();
24+
if(i==(size-1)) result.push_back(node->val); //将每一层的最后元素放入result数组中
25+
if(node->left) que.push(node->left);
26+
if(node->right) que.push(node->right);
27+
}
28+
}
29+
return result;
30+
}
31+
};
Collapse file

‎leetcode/medium/199_二叉树的右视图/199_二叉树的右视图.go‎

Copy file name to clipboard
+33Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* type TreeNode struct {
4+
* Val int
5+
* Left *TreeNode
6+
* Right *TreeNode
7+
* }
8+
*/
9+
func rightSideView(root *TreeNode) []int {
10+
res := []int{}
11+
if root == nil {
12+
return res
13+
}
14+
15+
q := []*TreeNode{root}
16+
for len(q) > 0 {
17+
size := len(q)
18+
for i := 0; i < size; i++ {
19+
node := q[0]
20+
q = q[1:]
21+
if i == size-1 {
22+
res = append(res, node.Val)
23+
}
24+
if node.Left != nil {
25+
q = append(q, node.Left)
26+
}
27+
if node.Right != nil {
28+
q = append(q, node.Right)
29+
}
30+
}
31+
}
32+
return res
33+
}
Collapse file

‎leetcode/medium/199_二叉树的右视图/199_二叉树的右视图.py‎

Copy file name to clipboard
+26Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
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+
class Solution:
8+
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
9+
if not root:
10+
return []
11+
12+
result: List[int] = []
13+
q = collections.deque([root])
14+
15+
while q:
16+
size = len(q)
17+
for i in range(size):
18+
node = q.popleft()
19+
if i == size - 1:
20+
result.append(node.val)
21+
if node.left:
22+
q.append(node.left)
23+
if node.right:
24+
q.append(node.right)
25+
26+
return result
Collapse file

‎leetcode/medium/199_二叉树的右视图/README.md‎

Copy file name to clipboard
+92Lines changed: 92 additions & 0 deletions
  • Display the source diff
  • Display the rich diff
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,92 @@
1+
# 199. 二叉树的右视图
2+
3+
- **平台**：LeetCode
4+
- **链接**：https://leetcode.cn/problems/binary-tree-right-side-view/description/
5+
- **难度**：Medium
6+
- **标签**：树、深度优先搜索、广度优先搜索、二叉树
7+
8+
## 题目描述
9+
10+
给定一个二叉树的根节点 `root`，想象你站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
11+
12+
## 示例
13+
14+
**示例 1：**
15+
```
16+
输入：root = [1,2,3,null,5,null,4]
17+
输出：[1,3,4]
18+
```
19+
20+
**示例 2：**
21+
```
22+
输入：root = [1,null,3]
23+
输出：[1,3]
24+
```
25+
26+
**示例 3：**
27+
```
28+
输入：root = []
29+
输出：[]
30+
```
31+
32+
## 解题思路
33+
34+
### 方法一：迭代（广度优先搜索 BFS）
35+
36+
#### 思路与算法
37+
38+
右视图等价于：**每一层最右侧（最后被遍历到）的那个节点**。
39+
40+
用 BFS 层序遍历即可：
41+
42+
1. 使用队列按层遍历二叉树。
43+
2. 每次循环前记录当前层节点数 `size`。
44+
3. 依次弹出当前层的 `size` 个节点：
45+
- 当 `i == size - 1` 时，说明该节点是本层最后一个节点（也就是最右侧能看到的节点），将其值加入答案。
46+
- 将其左右孩子按顺序入队。
47+
48+
## 代码实现
49+
50+
### C++
51+
52+
```cpp
53+
class Solution {
54+
public:
55+
vector<int> rightSideView(TreeNode* root) {
56+
queue<TreeNode*> que;
57+
if (root != NULL) que.push(root);
58+
vector<int> result;
59+
while (!que.empty()) {
60+
int size = que.size();
61+
for (int i = 0; i < size; i++) {
62+
TreeNode* node = que.front();
63+
que.pop();
64+
if (i == size - 1) result.push_back(node->val); // 将每一层的最后元素放入 result 中
65+
if (node->left) que.push(node->left);
66+
if (node->right) que.push(node->right);
67+
}
68+
}
69+
return result;
70+
}
71+
};
72+
```
73+
74+
### Python
75+
76+
详见 [199_二叉树的右视图.py](./199_二叉树的右视图.py)
77+
78+
### Go
79+
80+
详见 [199_二叉树的右视图.go](./199_二叉树的右视图.go)
81+
82+
## 复杂度分析
83+
84+
设节点数为 `n`。
85+
86+
- **时间复杂度**：每个点进队出队各一次，故渐进时间复杂度为 $O(n)$。
87+
- **空间复杂度**：队列中元素的个数不超过 $n$ 个，故渐进空间复杂度为 $O(n)$。
88+
89+
## 关键点
90+
91+
1. 右视图 = 每层的最后一个节点。
92+
2. BFS 分层遍历时一定要先记录固定的 `size`，避免队列长度在遍历过程中变化导致层边界出错。

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.