Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit febdb25

Browse filesBrowse files
2xiao2xiao
committed
Deploying to main from @ d246039 🚀
1 parent 7aeb4ca commit febdb25
Copy full SHA for febdb25

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.
Dismiss banner
Expand file treeCollapse file tree

51 files changed

+3916
-97
lines changed

‎book/greedy.md

Copy file name to clipboardExpand all lines: book/greedy.md
+1-1Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -33,7 +33,7 @@
3333
| 122 | 买卖股票的最佳时机 II | [[✓]](/problem/0122.md) | [`贪心`](/tag/greedy.md) [`数组`](/tag/array.md) [`动态规划`](/tag/dynamic-programming.md) | 🟠 | [🀄️](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii) [🔗](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii) |
3434
| 561 | 数组拆分 | [[✓]](/problem/0561.md) | [`贪心`](/tag/greedy.md) [`数组`](/tag/array.md) [`计数排序`](/tag/counting-sort.md) `1+` | 🟢 | [🀄️](https://leetcode.cn/problems/array-partition) [🔗](https://leetcode.com/problems/array-partition) |
3535
| 1710 | 卡车上的最大单元数 | | [`贪心`](/tag/greedy.md) [`数组`](/tag/array.md) [`排序`](/tag/sorting.md) | 🟢 | [🀄️](https://leetcode.cn/problems/maximum-units-on-a-truck) [🔗](https://leetcode.com/problems/maximum-units-on-a-truck) |
36-
| 1217 | 玩筹码 | | [`贪心`](/tag/greedy.md) [`数组`](/tag/array.md) [`数学`](/tag/math.md) | 🟢 | [🀄️](https://leetcode.cn/problems/minimum-cost-to-move-chips-to-the-same-position) [🔗](https://leetcode.com/problems/minimum-cost-to-move-chips-to-the-same-position) |
36+
| 1217 | 玩筹码 | [[✓]](/problem/1217.md) | [`贪心`](/tag/greedy.md) [`数组`](/tag/array.md) [`数学`](/tag/math.md) | 🟢 | [🀄️](https://leetcode.cn/problems/minimum-cost-to-move-chips-to-the-same-position) [🔗](https://leetcode.com/problems/minimum-cost-to-move-chips-to-the-same-position) |
3737
| 1247 | 交换字符使得字符串相同 | | [`贪心`](/tag/greedy.md) [`数学`](/tag/math.md) [`字符串`](/tag/string.md) | 🟠 | [🀄️](https://leetcode.cn/problems/minimum-swaps-to-make-strings-equal) [🔗](https://leetcode.com/problems/minimum-swaps-to-make-strings-equal) |
3838
| 1400 | 构造 K 个回文字符串 | | [`贪心`](/tag/greedy.md) [`哈希表`](/tag/hash-table.md) [`字符串`](/tag/string.md) `1+` | 🟠 | [🀄️](https://leetcode.cn/problems/construct-k-palindrome-strings) [🔗](https://leetcode.com/problems/construct-k-palindrome-strings) |
3939
| 921 | 使括号有效的最少添加 | [[✓]](/problem/0921.md) | [`栈`](/tag/stack.md) [`贪心`](/tag/greedy.md) [`字符串`](/tag/string.md) | 🟠 | [🀄️](https://leetcode.cn/problems/minimum-add-to-make-parentheses-valid) [🔗](https://leetcode.com/problems/minimum-add-to-make-parentheses-valid) |

‎book/sort.md

Copy file name to clipboardExpand all lines: book/sort.md
+1-1Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -401,7 +401,7 @@ function swap(arr, i, j) {
401401
| 题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
402402
| :------: | :------ | :------: | :------ | :------: | :------: |
403403
| 912 | 排序数组 | | [`数组`](/tag/array.md) [`分治`](/tag/divide-and-conquer.md) [`桶排序`](/tag/bucket-sort.md) `5+` | 🟠 | [🀄️](https://leetcode.cn/problems/sort-an-array) [🔗](https://leetcode.com/problems/sort-an-array) |
404-
| 1122 | 数组的相对排序 | | [`数组`](/tag/array.md) [`哈希表`](/tag/hash-table.md) [`计数排序`](/tag/counting-sort.md) `1+` | 🟢 | [🀄️](https://leetcode.cn/problems/relative-sort-array) [🔗](https://leetcode.com/problems/relative-sort-array) |
404+
| 1122 | 数组的相对排序 | [[✓]](/problem/1122.md) | [`数组`](/tag/array.md) [`哈希表`](/tag/hash-table.md) [`计数排序`](/tag/counting-sort.md) `1+` | 🟢 | [🀄️](https://leetcode.cn/problems/relative-sort-array) [🔗](https://leetcode.com/problems/relative-sort-array) |
405405

406406
* 桶排序
407407

‎plan/contest_list.md

Copy file name to clipboardExpand all lines: plan/contest_list.md
+25-25Lines changed: 25 additions & 25 deletions
Large diffs are not rendered by default.

‎plan/rabbit_list.md

Copy file name to clipboardExpand all lines: plan/rabbit_list.md
+1-1Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -234,7 +234,7 @@ headerDepth: 0
234234
| 387 | 字符串中的第一个唯一字符 | [[✓]](/problem/0387.md) | [`队列`](/tag/queue.md) [`哈希表`](/tag/hash-table.md) [`字符串`](/tag/string.md) `1+` | 🟢 | [🀄️](https://leetcode.cn/problems/first-unique-character-in-a-string) [🔗](https://leetcode.com/problems/first-unique-character-in-a-string) | 6 |
235235
| 173 | 二叉搜索树迭代器 | [[✓]](/problem/0173.md) | [`栈`](/tag/stack.md) [`树`](/tag/tree.md) [`设计`](/tag/design.md) `3+` | 🟠 | [🀄️](https://leetcode.cn/problems/binary-search-tree-iterator) [🔗](https://leetcode.com/problems/binary-search-tree-iterator) | 6 |
236236
| 17 | 电话号码的字母组合 | [[✓]](/problem/0017.md) | [`哈希表`](/tag/hash-table.md) [`字符串`](/tag/string.md) [`回溯`](/tag/backtracking.md) | 🟠 | [🀄️](https://leetcode.cn/problems/letter-combinations-of-a-phone-number) [🔗](https://leetcode.com/problems/letter-combinations-of-a-phone-number) | 6 |
237-
| 1200 | 最小绝对差 | | [`数组`](/tag/array.md) [`排序`](/tag/sorting.md) | 🟢 | [🀄️](https://leetcode.cn/problems/minimum-absolute-difference) [🔗](https://leetcode.com/problems/minimum-absolute-difference) | 6 |
237+
| 1200 | 最小绝对差 | [[✓]](/problem/1200.md) | [`数组`](/tag/array.md) [`排序`](/tag/sorting.md) | 🟢 | [🀄️](https://leetcode.cn/problems/minimum-absolute-difference) [🔗](https://leetcode.com/problems/minimum-absolute-difference) | 6 |
238238
| 545 | 二叉树的边界 🔒 | | [`树`](/tag/tree.md) [`深度优先搜索`](/tag/depth-first-search.md) [`二叉树`](/tag/binary-tree.md) | 🟠 | [🀄️](https://leetcode.cn/problems/boundary-of-binary-tree) [🔗](https://leetcode.com/problems/boundary-of-binary-tree) | 5 |
239239
| 841 | 钥匙和房间 | [[✓]](/problem/0841.md) | [`深度优先搜索`](/tag/depth-first-search.md) [`广度优先搜索`](/tag/breadth-first-search.md) [`图`](/tag/graph.md) | 🟠 | [🀄️](https://leetcode.cn/problems/keys-and-rooms) [🔗](https://leetcode.com/problems/keys-and-rooms) | 5 |
240240
| 1293 | 网格中的最短路径 | | [`广度优先搜索`](/tag/breadth-first-search.md) [`数组`](/tag/array.md) [`矩阵`](/tag/matrix.md) | 🔴 | [🀄️](https://leetcode.cn/problems/shortest-path-in-a-grid-with-obstacles-elimination) [🔗](https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination) | 5 |

‎plan/top_300_list.md

Copy file name to clipboardExpand all lines: plan/top_300_list.md
+3-3Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -224,7 +224,7 @@ headerDepth: 0
224224
<!-- prettier-ignore -->
225225
| 题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
226226
| :------: | :------ | :------: | :------ | :------: | :------: |
227-
| 1046 | 最后一块石头的重量 | | [`数组`](/tag/array.md) [`堆（优先队列）`](/tag/heap-priority-queue.md) | 🟢 | [🀄️](https://leetcode.cn/problems/last-stone-weight) [🔗](https://leetcode.com/problems/last-stone-weight) |
227+
| 1046 | 最后一块石头的重量 | [[✓]](/problem/1046.md) | [`数组`](/tag/array.md) [`堆（优先队列）`](/tag/heap-priority-queue.md) | 🟢 | [🀄️](https://leetcode.cn/problems/last-stone-weight) [🔗](https://leetcode.com/problems/last-stone-weight) |
228228
| 703 | 数据流中的第 K 大元素 | [[✓]](/problem/0703.md) | [`树`](/tag/tree.md) [`设计`](/tag/design.md) [`二叉搜索树`](/tag/binary-search-tree.md) `3+` | 🟢 | [🀄️](https://leetcode.cn/problems/kth-largest-element-in-a-stream) [🔗](https://leetcode.com/problems/kth-largest-element-in-a-stream) |
229229
| 215 | 数组中的第K个最大元素 | [[✓]](/problem/0215.md) | [`数组`](/tag/array.md) [`分治`](/tag/divide-and-conquer.md) [`快速选择`](/tag/quickselect.md) `2+` | 🟠 | [🀄️](https://leetcode.cn/problems/kth-largest-element-in-an-array) [🔗](https://leetcode.com/problems/kth-largest-element-in-an-array) |
230230
| 347 | 前 K 个高频元素 | [[✓]](/problem/0347.md) | [`数组`](/tag/array.md) [`哈希表`](/tag/hash-table.md) [`分治`](/tag/divide-and-conquer.md) `5+` | 🟠 | [🀄️](https://leetcode.cn/problems/top-k-frequent-elements) [🔗](https://leetcode.com/problems/top-k-frequent-elements) |
@@ -548,7 +548,7 @@ headerDepth: 0
548548
| 628 | 三个数的最大乘积 | [[✓]](/problem/0628.md) | [`数组`](/tag/array.md) [`数学`](/tag/math.md) [`排序`](/tag/sorting.md) | 🟢 | [🀄️](https://leetcode.cn/problems/maximum-product-of-three-numbers) [🔗](https://leetcode.com/problems/maximum-product-of-three-numbers) |
549549
| 976 | 三角形的最大周长 | [[✓]](/problem/0976.md) | [`贪心`](/tag/greedy.md) [`数组`](/tag/array.md) [`数学`](/tag/math.md) `1+` | 🟢 | [🀄️](https://leetcode.cn/problems/largest-perimeter-triangle) [🔗](https://leetcode.com/problems/largest-perimeter-triangle) |
550550
| 202 | 快乐数 | [[✓]](/problem/0202.md) | [`哈希表`](/tag/hash-table.md) [`数学`](/tag/math.md) [`双指针`](/tag/two-pointers.md) | 🟢 | [🀄️](https://leetcode.cn/problems/happy-number) [🔗](https://leetcode.com/problems/happy-number) |
551-
| 1232 | 缀点成线 | | [`几何`](/tag/geometry.md) [`数组`](/tag/array.md) [`数学`](/tag/math.md) | 🟢 | [🀄️](https://leetcode.cn/problems/check-if-it-is-a-straight-line) [🔗](https://leetcode.com/problems/check-if-it-is-a-straight-line) |
551+
| 1232 | 缀点成线 | [[✓]](/problem/1232.md) | [`几何`](/tag/geometry.md) [`数组`](/tag/array.md) [`数学`](/tag/math.md) | 🟢 | [🀄️](https://leetcode.cn/problems/check-if-it-is-a-straight-line) [🔗](https://leetcode.com/problems/check-if-it-is-a-straight-line) |
552552
| 29 | 两数相除 | [[✓]](/problem/0029.md) | [`位运算`](/tag/bit-manipulation.md) [`数学`](/tag/math.md) | 🟠 | [🀄️](https://leetcode.cn/problems/divide-two-integers) [🔗](https://leetcode.com/problems/divide-two-integers) |
553553
| 343 | 整数拆分 | [[✓]](/problem/0343.md) | [`数学`](/tag/math.md) [`动态规划`](/tag/dynamic-programming.md) | 🟠 | [🀄️](https://leetcode.cn/problems/integer-break) [🔗](https://leetcode.com/problems/integer-break) |
554554
| 166 | 分数到小数 | | [`哈希表`](/tag/hash-table.md) [`数学`](/tag/math.md) [`字符串`](/tag/string.md) | 🟠 | [🀄️](https://leetcode.cn/problems/fraction-to-recurring-decimal) [🔗](https://leetcode.com/problems/fraction-to-recurring-decimal) |
@@ -574,7 +574,7 @@ headerDepth: 0
574574
<!-- prettier-ignore -->
575575
| 题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
576576
| :------: | :------ | :------: | :------ | :------: | :------: |
577-
| 1232 | 缀点成线 | | [`几何`](/tag/geometry.md) [`数组`](/tag/array.md) [`数学`](/tag/math.md) | 🟢 | [🀄️](https://leetcode.cn/problems/check-if-it-is-a-straight-line) [🔗](https://leetcode.com/problems/check-if-it-is-a-straight-line) |
577+
| 1232 | 缀点成线 | [[✓]](/problem/1232.md) | [`几何`](/tag/geometry.md) [`数组`](/tag/array.md) [`数学`](/tag/math.md) | 🟢 | [🀄️](https://leetcode.cn/problems/check-if-it-is-a-straight-line) [🔗](https://leetcode.com/problems/check-if-it-is-a-straight-line) |
578578
| 1266 | 访问所有点的最小时间 | | [`几何`](/tag/geometry.md) [`数组`](/tag/array.md) [`数学`](/tag/math.md) | 🟢 | [🀄️](https://leetcode.cn/problems/minimum-time-visiting-all-points) [🔗](https://leetcode.com/problems/minimum-time-visiting-all-points) |
579579
| 892 | 三维形体的表面积 | [[✓]](/problem/0892.md) | [`几何`](/tag/geometry.md) [`数组`](/tag/array.md) [`数学`](/tag/math.md) `1+` | 🟢 | [🀄️](https://leetcode.cn/problems/surface-area-of-3d-shapes) [🔗](https://leetcode.com/problems/surface-area-of-3d-shapes) |
580580
| 1401 | 圆和矩形是否有重叠 | | [`几何`](/tag/geometry.md) [`数学`](/tag/math.md) | 🟠 | [🀄️](https://leetcode.cn/problems/circle-and-rectangle-overlapping) [🔗](https://leetcode.com/problems/circle-and-rectangle-overlapping) |

‎problem/0383.md

Copy file name to clipboardExpand all lines: problem/0383.md
+1-1Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -101,4 +101,4 @@ var canConstruct = function (ransomNote, magazine) {
101101
| 题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
102102
| :------: | :------ | :------: | :------ | :------: | :------: |
103103
| 691 | 贴纸拼词 | | [`位运算`](/tag/bit-manipulation.md) [`数组`](/tag/array.md) [`字符串`](/tag/string.md) `3+` | 🔴 | [🀄️](https://leetcode.cn/problems/stickers-to-spell-word) [🔗](https://leetcode.com/problems/stickers-to-spell-word) |
104-
| 1160 | 拼写单词 | | [`数组`](/tag/array.md) [`哈希表`](/tag/hash-table.md) [`字符串`](/tag/string.md) `1+` | 🟢 | [🀄️](https://leetcode.cn/problems/find-words-that-can-be-formed-by-characters) [🔗](https://leetcode.com/problems/find-words-that-can-be-formed-by-characters) |
104+
| 1160 | 拼写单词 | [[✓]](/problem/1160.md) | [`数组`](/tag/array.md) [`哈希表`](/tag/hash-table.md) [`字符串`](/tag/string.md) `1+` | 🟢 | [🀄️](https://leetcode.cn/problems/find-words-that-can-be-formed-by-characters) [🔗](https://leetcode.com/problems/find-words-that-can-be-formed-by-characters) |

‎problem/1022.md

Copy file name to clipboard
+142Lines changed: 142 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,142 @@
1+
---
2+
title: 1022. 从根到叶的二进制数之和
3+
description: LeetCode 1022. 从根到叶的二进制数之和题解，Sum of Root To Leaf Binary Numbers，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。
4+
keywords:
5+
- LeetCode
6+
- 1022. 从根到叶的二进制数之和
7+
- 从根到叶的二进制数之和
8+
- Sum of Root To Leaf Binary Numbers
9+
- 解题思路
10+
- 树
11+
- 深度优先搜索
12+
- 二叉树
13+
---
14+
15+
# 1022. 从根到叶的二进制数之和
16+
17+
🟢 <font color=#15bd66>Easy</font>&emsp; 🔖&ensp; [`树`](/tag/tree.md) [`深度优先搜索`](/tag/depth-first-search.md) [`二叉树`](/tag/binary-tree.md)&emsp; 🔗&ensp;[`力扣`](https://leetcode.cn/problems/sum-of-root-to-leaf-binary-numbers) [`LeetCode`](https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers)
18+
19+
## 题目
20+
21+
You are given the `root` of a binary tree where each node has a value `0` or
22+
`1`. Each root-to-leaf path represents a binary number starting with the most
23+
significant bit.
24+
25+
- For example, if the path is `0 -> 1 -> 1 -> 0 -> 1`, then this could represent `01101` in binary, which is `13`.
26+
27+
For all leaves in the tree, consider the numbers represented by the path from
28+
the root to that leaf. Return _the sum of these numbers_.
29+
30+
The test cases are generated so that the answer fits in a **32-bits** integer.
31+
32+
**Example 1:**
33+
34+
![](https://assets.leetcode.com/uploads/2019/04/04/sum-of-root-to-leaf-binary-
35+
numbers.png)
36+
37+
> Input: root = [1,0,1,0,1,0,1]
38+
>
39+
> Output: 22
40+
>
41+
> Explanation:(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
42+
43+
**Example 2:**
44+
45+
> Input: root = [0]
46+
>
47+
> Output: 0
48+
49+
**Constraints:**
50+
51+
- The number of nodes in the tree is in the range `[1, 1000]`.
52+
- `Node.val` is `0` or `1`.
53+
54+
## 题目大意
55+
56+
给出一棵二叉树，其上每个结点的值都是 `0` 或 `1` 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。
57+
58+
- 例如，如果路径为 `0 -> 1 -> 1 -> 0 -> 1`，那么它表示二进制数 `01101`，也就是 `13` 。
59+
60+
对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。
61+
62+
返回这些数字之和。题目数据保证答案是一个 **32 位** 整数。
63+
64+
**示例 1：**
65+
66+
![](https://assets.leetcode.com/uploads/2019/04/04/sum-of-root-to-leaf-binary-
67+
numbers.png)
68+
69+
> **输入：** root = [1,0,1,0,1,0,1]
70+
>
71+
> **输出：** 22
72+
>
73+
> **解释：**(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
74+
75+
**示例 2：**
76+
77+
> **输入：** root = [0]
78+
>
79+
> **输出：** 0
80+
81+
**提示：**
82+
83+
- 树中的节点数在 `[1, 1000]` 范围内
84+
- `Node.val` 仅为 `0` 或 `1`
85+
86+
## 解题思路
87+
88+
我们可以通过 **深度优先搜索（DFS）** 来实现这一目标。
89+
90+
1. **深度优先搜索（DFS）**：
91+
92+
- 从根节点开始遍历，每次向下递归时，将父节点的值左移一位（相当于将二进制数向左移动一位）后加上当前节点的值，生成新的路径值。
93+
- 如果当前节点是叶子节点（没有左子节点和右子节点），则将当前路径值累加到结果中。
94+
95+
2. **递归传递路径值**：
96+
97+
- 每次递归时，将当前路径值作为参数传递到下一层，表示从根节点到当前节点的路径值。
98+
- 当遍历到叶子节点时，直接将该路径值加到结果变量中。
99+
100+
3. **返回结果**：
101+
- 遍历完整棵树后，返回累加的路径值总和。
102+
103+
#### 复杂度分析
104+
105+
- **时间复杂度**：`O(n)`，其中 `n` 是二叉树的节点总数，每个节点都被访问一次。
106+
- **空间复杂度**：`O(h)`，其中 `h` 是树的高度，递归调用栈的深度为树的高度，
107+
- 最坏情况下（树为链状），`h = n`；
108+
- 最好情况下（树为完全平衡树），`h = log(n)`。
109+
110+
## 代码
111+
112+
```javascript
113+
/**
114+
* @param {TreeNode} root
115+
* @return {number}
116+
*/
117+
var sumRootToLeaf = function (root) {
118+
let sum = 0; // 用于存储路径值的总和
119+
120+
// 定义递归函数
121+
const dfs = (root, parent) => {
122+
if (!root) return; // 如果节点为空，直接返回
123+
124+
// 更新当前路径值
125+
const cur = (parent << 1) | root.val;
126+
127+
// 如果当前节点是叶子节点
128+
if (!root.left && !root.right) {
129+
sum += cur; // 将路径值累加到总和中
130+
} else {
131+
// 递归遍历左子树和右子树
132+
dfs(root.left, cur);
133+
dfs(root.right, cur);
134+
}
135+
};
136+
137+
// 从根节点开始 DFS，初始路径值为 0
138+
dfs(root, 0);
139+
140+
return sum; // 返回路径值的总和
141+
};
142+
```

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.