-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path226.py
161 lines (108 loc) · 3.52 KB
/
226.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
# leetcode 226 反转二叉树
# 第一种 递归法 前序遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
# 第二种 迭代法 前序遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
stack = [root]
while stack:
tmp = stack.pop()
tmp.left, tmp.right = tmp.right, tmp.left
if tmp.left:
stack.append(tmp.left)
if tmp.right:
stack.append(tmp.right)
return root
# 递归法 中序遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
self.invertTree(root.left)
root.left, root.right = root.right, root.left
# 这里注意两次都是反转左边 因为上面左右交换了
self.invertTree(root.left)
return root
# 迭代法 中序遍历
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
stack = [root]
while stack:
tmp = stack.pop()
if tmp.left:
stack.append(tmp.left)
tmp.left, tmp.right = tmp.right, tmp.left
if tmp.left:
stack.append(tmp.left)
return root
# 后序遍历 递归法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
self.invertTree(root.right)
self.invertTree(root.left)
root.left, root.right = root.right, root.left
return root
# 层序遍历 迭代法
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
from collections import deque
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
queue = deque([root])
while queue:
tmp = queue.popleft()
if tmp.right:
queue.append(tmp.right)
tmp.left, tmp.right = tmp.right, tmp.left
if tmp.right:
queue.append(tmp.right)
return root