Skip to content

Commit 7ccc8d8

Browse files
gazeldxgazeldx
committed
144-binary-tree-preorder-traversal.md Adde Python solution in 2 ways.
1 parent 947ce9d commit 7ccc8d8

5 files changed

Lines changed: 277 additions & 1 deletion

File tree

‎en/1-1000/144-binary-tree-preorder-traversal.md‎

Lines changed: 139 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,139 @@
1+
# 144. Binary Tree Preorder Traversal - Best Practices of LeetCode Solutions
2+
LeetCode link: [144. Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal), difficulty: **Easy**.
3+
4+
## LeetCode description of "144. Binary Tree Preorder Traversal"
5+
Given the `root` of a binary tree, return _the preorder traversal of its nodes' values_.
6+
7+
### [Example 1]
8+
9+
**Input**: `root = [1,null,2,3]`
10+
11+
**Output**: `[1,2,3]`
12+
13+
**Explanation**:
14+
15+
![](../../images/examples/144_1.png)
16+
17+
### [Example 2]
18+
19+
**Input**: `root = [1,2,3,4,5,null,8,null,null,6,7,9]`
20+
21+
**Output**: `[1,2,4,5,6,7,3,8,9]`
22+
23+
**Explanation**:
24+
25+
![](../../images/examples/144_2.png)
26+
27+
### [Example 3]
28+
29+
**Input**: `root = []`
30+
31+
**Output**: `[]`
32+
33+
### [Example 4]
34+
35+
**Input**: `root = [1]`
36+
37+
**Output**: `[1]`
38+
39+
### [Constraints]
40+
- The number of nodes in the tree is in the range `[0, 100]`.
41+
- `-100 <= Node.val <= 100`
42+
43+
## Intuition
44+
Will be added later.
45+
46+
## Steps
47+
Will be added later.
48+
49+
## Complexity
50+
Recursive solution and iterative solution are equal in complexity.
51+
52+
* Time: `O(N)`.
53+
* Space: `O(N)`.
54+
55+
## Follow-up
56+
Recursive solution is trivial, could you do it iteratively?
57+
58+
## Follow-up intuition
59+
Will be added later.
60+
61+
## Python
62+
### Solution 1: Recursion
63+
```python
64+
class Solution:
65+
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
66+
self.values = []
67+
68+
self.traverse(root)
69+
70+
return self.values
71+
72+
def traverse(self, node):
73+
if node is None:
74+
return
75+
76+
self.values.append(node.val)
77+
78+
self.traverse(node.left)
79+
80+
self.traverse(node.right)
81+
```
82+
83+
### Solution 2: Iteration
84+
```python
85+
class Solution:
86+
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
87+
values = []
88+
stack = []
89+
90+
if root:
91+
stack.append(root)
92+
93+
while stack:
94+
node = stack.pop()
95+
values.append(node.val)
96+
97+
if node.right:
98+
stack.append(node.right)
99+
100+
if node.left:
101+
stack.append(node.left)
102+
103+
return values
104+
```
105+
106+
## JavaScript
107+
```javascript
108+
// Welcome to create a PR to complete the code of this language, thanks!
109+
```
110+
111+
## Java
112+
```java
113+
// Welcome to create a PR to complete the code of this language, thanks!
114+
```
115+
116+
## C++
117+
```cpp
118+
// Welcome to create a PR to complete the code of this language, thanks!
119+
```
120+
121+
## C#
122+
```c#
123+
// Welcome to create a PR to complete the code of this language, thanks!
124+
```
125+
126+
## Go
127+
```go
128+
// Welcome to create a PR to complete the code of this language, thanks!
129+
```
130+
131+
## Ruby
132+
```ruby
133+
# Welcome to create a PR to complete the code of this language, thanks!
134+
```
135+
136+
## C, Kotlin, Swift, Rust or other languages
137+
```
138+
// Welcome to create a PR to complete the code of this language, thanks!
139+
```

‎images/examples/144_1.png‎

9.22 KB
Loading

‎images/examples/144_2.png‎

25.4 KB
Loading

‎zh/1-1000/144-binary-tree-preorder-traversal.md‎

Lines changed: 137 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,137 @@
1+
# 144. 二叉树的前序遍历 - 力扣题解最佳实践
2+
力扣链接：[144. 二叉树的前序遍历](https://leetcode.cn/problems/binary-tree-preorder-traversal) ，难度：**容易**。
3+
4+
## 力扣“144. 二叉树的前序遍历”问题描述
5+
给你二叉树的根节点 `root` ，返回它节点值的 **前序** 遍历。
6+
7+
### [示例 1]
8+
9+
**输入**: `root = [1,null,2,3]`
10+
11+
**输出**: `[1,2,3]`
12+
13+
**解释**:
14+
15+
![](../../images/examples/144_1.png)
16+
17+
### [示例 2]
18+
19+
**输入**: `root = [1,2,3,4,5,null,8,null,null,6,7,9]`
20+
21+
**输出**: `[1,2,4,5,6,7,3,8,9]`
22+
23+
**解释**:
24+
25+
![](../../images/examples/144_2.png)
26+
27+
### [示例 3]
28+
29+
**输入**: `root = []`
30+
31+
**输出**: `[]`
32+
33+
### [示例 4]
34+
35+
**输入**: `root = [1]`
36+
37+
**输出**: `[1]`
38+
39+
### [约束]
40+
- 树中节点数目在范围 `[0, 100]` 内
41+
- `-100 <= Node.val <= 100`
42+
43+
## 思路
44+
以后会被添加。
45+
46+
## 步骤
47+
以后会被添加。
48+
49+
## 复杂度
50+
* 时间：`O(N)`。
51+
* 空间：`O(N)`。
52+
53+
## 进阶
54+
递归算法很简单，你可以通过迭代算法完成吗？
55+
56+
## 进阶思路
57+
以后会被添加。
58+
59+
## Python
60+
### Solution 1: Recursion
61+
```python
62+
class Solution:
63+
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
64+
self.values = []
65+
66+
self.traverse(root)
67+
68+
return self.values
69+
70+
def traverse(self, node):
71+
if node is None:
72+
return
73+
74+
self.values.append(node.val)
75+
76+
self.traverse(node.left)
77+
78+
self.traverse(node.right)
79+
```
80+
81+
### Solution 2: Iteration
82+
```python
83+
class Solution:
84+
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
85+
values = []
86+
stack = []
87+
88+
if root:
89+
stack.append(root)
90+
91+
while stack:
92+
node = stack.pop()
93+
values.append(node.val)
94+
95+
if node.right:
96+
stack.append(node.right)
97+
98+
if node.left:
99+
stack.append(node.left)
100+
101+
return values
102+
```
103+
104+
## JavaScript
105+
```javascript
106+
// Welcome to create a PR to complete the code of this language, thanks!
107+
```
108+
109+
## Java
110+
```java
111+
// Welcome to create a PR to complete the code of this language, thanks!
112+
```
113+
114+
## C++
115+
```cpp
116+
// Welcome to create a PR to complete the code of this language, thanks!
117+
```
118+
119+
## C#
120+
```c#
121+
// Welcome to create a PR to complete the code of this language, thanks!
122+
```
123+
124+
## Go
125+
```go
126+
// Welcome to create a PR to complete the code of this language, thanks!
127+
```
128+
129+
## Ruby
130+
```ruby
131+
# Welcome to create a PR to complete the code of this language, thanks!
132+
```
133+
134+
## C, Kotlin, Swift, Rust or other languages
135+
```
136+
// Welcome to create a PR to complete the code of this language, thanks!
137+
```

‎zh/1-1000/209-minimum-size-subarray-sum.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,7 @@
1313

1414
**输出**: `2`
1515

16-
**解释**: `子数组 _[4,3]_ 是该条件下的长度最小的子数组。`
16+
**解释**: `子数组 [4,3] 是该条件下的长度最小的子数组。`
1717

1818
### [示例 2]
1919
**输入**: `target = 4, nums = [1,4,4]`

0 commit comments

Comments
 (0)