Skip to content

Commit 0338ae8

Browse files
committed
feat: add solutions to lc problem: No.0226
No.0226.Invert Binary Tree
1 parent 36bc6c6 commit 0338ae8

File tree

7 files changed

+138
-43
lines changed

7 files changed

+138
-43
lines changed

solution/0200-0299/0226.Invert Binary Tree/README.md

Lines changed: 51 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -48,7 +48,11 @@
4848

4949
<!-- 这里可写通用的实现逻辑 -->
5050

51-
DFS。
51+
**方法一:递归**
52+
53+
递归的思路很简单,就是交换当前节点的左右子树,然后递归地交换当前节点的左右子树。
54+
55+
时间复杂度 $O(n)$,空间复杂度 $O(n)$。其中 $n$ 是二叉树的节点个数。
5256

5357
<!-- tabs:start -->
5458

@@ -64,7 +68,7 @@ DFS。
6468
# self.left = left
6569
# self.right = right
6670
class Solution:
67-
def invertTree(self, root: TreeNode) -> TreeNode:
71+
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
6872
def dfs(root):
6973
if root is None:
7074
return
@@ -132,18 +136,17 @@ class Solution {
132136
class Solution {
133137
public:
134138
TreeNode* invertTree(TreeNode* root) {
139+
function<void(TreeNode*)> dfs = [&](TreeNode* root) {
140+
if (!root) {
141+
return;
142+
}
143+
swap(root->left, root->right);
144+
dfs(root->left);
145+
dfs(root->right);
146+
};
135147
dfs(root);
136148
return root;
137149
}
138-
139-
void dfs(TreeNode* root) {
140-
if (!root) return;
141-
TreeNode* t = root->left;
142-
root->left = root->right;
143-
root->right = t;
144-
dfs(root->left);
145-
dfs(root->right);
146-
}
147150
};
148151
```
149152
@@ -159,7 +162,7 @@ public:
159162
* }
160163
*/
161164
func invertTree(root *TreeNode) *TreeNode {
162-
var dfs func(root *TreeNode)
165+
var dfs func(*TreeNode)
163166
dfs = func(root *TreeNode) {
164167
if root == nil {
165168
return
@@ -189,17 +192,50 @@ func invertTree(root *TreeNode) *TreeNode {
189192
* @return {TreeNode}
190193
*/
191194
var invertTree = function (root) {
192-
function dfs(root) {
193-
if (!root) return;
195+
const dfs = root => {
196+
if (!root) {
197+
return;
198+
}
194199
[root.left, root.right] = [root.right, root.left];
195200
dfs(root.left);
196201
dfs(root.right);
197-
}
202+
};
198203
dfs(root);
199204
return root;
200205
};
201206
```
202207

208+
### **TypeScript**
209+
210+
```ts
211+
/**
212+
* Definition for a binary tree node.
213+
* class TreeNode {
214+
* val: number
215+
* left: TreeNode | null
216+
* right: TreeNode | null
217+
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
218+
* this.val = (val===undefined ? 0 : val)
219+
* this.left = (left===undefined ? null : left)
220+
* this.right = (right===undefined ? null : right)
221+
* }
222+
* }
223+
*/
224+
225+
function invertTree(root: TreeNode | null): TreeNode | null {
226+
const dfs = (root: TreeNode | null) => {
227+
if (root === null) {
228+
return;
229+
}
230+
[root.left, root.right] = [root.right, root.left];
231+
dfs(root.left);
232+
dfs(root.right);
233+
};
234+
dfs(root);
235+
return root;
236+
}
237+
```
238+
203239
### **...**
204240

205241
```

solution/0200-0299/0226.Invert Binary Tree/README_EN.md

Lines changed: 46 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -52,7 +52,7 @@ DFS.
5252
# self.left = left
5353
# self.right = right
5454
class Solution:
55-
def invertTree(self, root: TreeNode) -> TreeNode:
55+
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
5656
def dfs(root):
5757
if root is None:
5858
return
@@ -118,18 +118,17 @@ class Solution {
118118
class Solution {
119119
public:
120120
TreeNode* invertTree(TreeNode* root) {
121+
function<void(TreeNode*)> dfs = [&](TreeNode* root) {
122+
if (!root) {
123+
return;
124+
}
125+
swap(root->left, root->right);
126+
dfs(root->left);
127+
dfs(root->right);
128+
};
121129
dfs(root);
122130
return root;
123131
}
124-
125-
void dfs(TreeNode* root) {
126-
if (!root) return;
127-
TreeNode* t = root->left;
128-
root->left = root->right;
129-
root->right = t;
130-
dfs(root->left);
131-
dfs(root->right);
132-
}
133132
};
134133
```
135134
@@ -145,7 +144,7 @@ public:
145144
* }
146145
*/
147146
func invertTree(root *TreeNode) *TreeNode {
148-
var dfs func(root *TreeNode)
147+
var dfs func(*TreeNode)
149148
dfs = func(root *TreeNode) {
150149
if root == nil {
151150
return
@@ -175,17 +174,50 @@ func invertTree(root *TreeNode) *TreeNode {
175174
* @return {TreeNode}
176175
*/
177176
var invertTree = function (root) {
178-
function dfs(root) {
179-
if (!root) return;
177+
const dfs = root => {
178+
if (!root) {
179+
return;
180+
}
180181
[root.left, root.right] = [root.right, root.left];
181182
dfs(root.left);
182183
dfs(root.right);
183-
}
184+
};
184185
dfs(root);
185186
return root;
186187
};
187188
```
188189

190+
### **TypeScript**
191+
192+
```ts
193+
/**
194+
* Definition for a binary tree node.
195+
* class TreeNode {
196+
* val: number
197+
* left: TreeNode | null
198+
* right: TreeNode | null
199+
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
200+
* this.val = (val===undefined ? 0 : val)
201+
* this.left = (left===undefined ? null : left)
202+
* this.right = (right===undefined ? null : right)
203+
* }
204+
* }
205+
*/
206+
207+
function invertTree(root: TreeNode | null): TreeNode | null {
208+
const dfs = (root: TreeNode | null) => {
209+
if (root === null) {
210+
return;
211+
}
212+
[root.left, root.right] = [root.right, root.left];
213+
dfs(root.left);
214+
dfs(root.right);
215+
};
216+
dfs(root);
217+
return root;
218+
}
219+
```
220+
189221
### **...**
190222

191223
```

solution/0200-0299/0226.Invert Binary Tree/Solution.cpp

Lines changed: 8 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -12,16 +12,15 @@
1212
class Solution {
1313
public:
1414
TreeNode* invertTree(TreeNode* root) {
15+
function<void(TreeNode*)> dfs = [&](TreeNode* root) {
16+
if (!root) {
17+
return;
18+
}
19+
swap(root->left, root->right);
20+
dfs(root->left);
21+
dfs(root->right);
22+
};
1523
dfs(root);
1624
return root;
1725
}
18-
19-
void dfs(TreeNode* root) {
20-
if (!root) return;
21-
TreeNode* t = root->left;
22-
root->left = root->right;
23-
root->right = t;
24-
dfs(root->left);
25-
dfs(root->right);
26-
}
2726
};

solution/0200-0299/0226.Invert Binary Tree/Solution.go

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
* }
88
*/
99
func invertTree(root *TreeNode) *TreeNode {
10-
var dfs func(root *TreeNode)
10+
var dfs func(*TreeNode)
1111
dfs = func(root *TreeNode) {
1212
if root == nil {
1313
return

solution/0200-0299/0226.Invert Binary Tree/Solution.js

Lines changed: 5 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -11,12 +11,14 @@
1111
* @return {TreeNode}
1212
*/
1313
var invertTree = function (root) {
14-
function dfs(root) {
15-
if (!root) return;
14+
const dfs = root => {
15+
if (!root) {
16+
return;
17+
}
1618
[root.left, root.right] = [root.right, root.left];
1719
dfs(root.left);
1820
dfs(root.right);
19-
}
21+
};
2022
dfs(root);
2123
return root;
2224
};

solution/0200-0299/0226.Invert Binary Tree/Solution.py

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@
55
# self.left = left
66
# self.right = right
77
class Solution:
8-
def invertTree(self, root: TreeNode) -> TreeNode:
8+
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
99
def dfs(root):
1010
if root is None:
1111
return
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* class TreeNode {
4+
* val: number
5+
* left: TreeNode | null
6+
* right: TreeNode | null
7+
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8+
* this.val = (val===undefined ? 0 : val)
9+
* this.left = (left===undefined ? null : left)
10+
* this.right = (right===undefined ? null : right)
11+
* }
12+
* }
13+
*/
14+
15+
function invertTree(root: TreeNode | null): TreeNode | null {
16+
const dfs = (root: TreeNode | null) => {
17+
if (root === null) {
18+
return;
19+
}
20+
[root.left, root.right] = [root.right, root.left];
21+
dfs(root.left);
22+
dfs(root.right);
23+
};
24+
dfs(root);
25+
return root;
26+
}

0 commit comments

Comments
 (0)