Skip to content

Commit d72a4c5

Browse files
daachengdaacheng
committed
反转二叉树
反转二叉树
1 parent fedcc87 commit d72a4c5

File tree

11 files changed

+272
-0
lines changed

11 files changed

+272
-0
lines changed

‎leetcode_tree/main.md‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -28,7 +28,21 @@
2828
#### 平衡二叉搜索树
2929
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
3030

31+
#### 二叉树的遍历
32+
* 二叉树的遍历分为前序遍历，中序遍历，后序遍历，和层次遍历
33+
* 前序遍历：根左右，先遍历根节点，再遍历左子树，然后遍历右子树
34+
* 中序遍历：左根右，先遍历左子树，再遍历根节点，最后遍历右子树
35+
* 后序遍历：左右根，先遍历左子树，再遍历右子树，最后遍历根节点
36+
* 层次遍历：从上向下，从左向右遍历
37+
38+
![](../pic/leetcode_tree/bianlitree.png)
39+
3140
## 2.题目
41+
* [二叉树的前序遍历](二叉树的前序遍历.md)
42+
* [二叉树的中序遍历](二叉树的中序遍历.md)
43+
* [二叉树的后序遍历](二叉树的后序遍历.md)
44+
* [二叉树的层序遍历](二叉树的层序遍历.md)
45+
* [反转二叉树](反转二叉树.md)
3246

3347
1. [相同的树](相同的树.md)
3448

‎leetcode_tree/二叉树的中序遍历.md‎

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
# 94.二叉树的中序遍历
2+
## 题目
3+
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
4+
5+
## 分析
6+
#### 递归
7+
中序遍历是按照 左子树-根节点-右子树的方式遍历 ，在访问左子树或右子树的时候，也是同样的方式遍历
8+
9+
```python
10+
class TreeNode:
11+
def __init__(self, val=0, left=None, right=None):
12+
self.val = val
13+
self.left = left
14+
self.right = right
15+
16+
17+
def inorderTraversal(root):
18+
def inorder(root):
19+
if not root:
20+
return
21+
inorder(root.left)
22+
ans.append(root.val)
23+
inorder(root.right)
24+
25+
ans = list()
26+
inorder(root)
27+
return ans
28+
29+
if __name__ == '__main__':
30+
root = TreeNode(1)
31+
node_1 = TreeNode(2)
32+
node_2 = TreeNode(3)
33+
root.left = node_1
34+
root.right = node_2
35+
36+
res = inorderTraversal(root)
37+
print(res)
38+
```
39+
40+
#### 迭代
41+
![](../pic/leetcode_tree/94_1.gif)
42+
43+
```python
44+
def inorderTraversal(root):
45+
ans = list()
46+
if not root:
47+
return ans
48+
49+
stack = []
50+
node = root
51+
while stack or node:
52+
while node:
53+
stack.append(node)
54+
node = node.left
55+
node = stack.pop()
56+
ans.append(node.val)
57+
node = node.right
58+
return ans
59+
```

‎leetcode_tree/二叉树的前序遍历.md‎

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
# 144.二叉树的前序遍历
2+
## 题目
3+
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
4+
5+
## 分析
6+
#### 递归
7+
前序遍历是按照 根节点-左子树-右子树的方式遍历 ，在访问左子树或右子树的时候，也是同样的方式遍历
8+
9+
```python
10+
class TreeNode:
11+
def __init__(self, val=0, left=None, right=None):
12+
self.val = val
13+
self.left = left
14+
self.right = right
15+
16+
17+
def preorderTraversal(root):
18+
def preorder(root):
19+
if not root:
20+
return
21+
ans.append(root.val)
22+
preorder(root.left)
23+
preorder(root.right)
24+
25+
ans = list()
26+
preorder(root)
27+
return ans
28+
```
29+
30+
#### 迭代
31+
* 利用栈，每遍历到非空节点，就记录节点的值(根)就入栈，然后继续遍历该节点的左节点(左)
32+
* 如果左节点为空，说明节点的做节点遍历完毕，结束循环，弹栈，开始遍历右节点，重复第一步
33+
34+
![](../pic/leetcode_tree/144_1.gif)
35+
36+
```python
37+
class TreeNode:
38+
def __init__(self, val=0, left=None, right=None):
39+
self.val = val
40+
self.left = left
41+
self.right = right
42+
43+
44+
def preorderTraversal(root):
45+
ans = list()
46+
if not root:
47+
return ans
48+
49+
stack = []
50+
node = root
51+
while stack or node:
52+
while node:
53+
ans.append(node.val)
54+
stack.append(node)
55+
node = node.left
56+
node = stack.pop()
57+
node = node.right
58+
return ans
59+
```

‎leetcode_tree/二叉树的后序遍历.md‎

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
# 145.二叉树的后序遍历
2+
## 题目
3+
给定一个二叉树，返回它的 后序 遍历。
4+
5+
## 分析
6+
#### 递归
7+
```python
8+
def postorderTraversal(root):
9+
def postorder(root):
10+
if not root:
11+
return
12+
postorder(root.left)
13+
postorder(root.right)
14+
ans.append(root.val)
15+
16+
ans = list()
17+
postorder(root)
18+
return ans
19+
```
20+
21+
## 迭代
22+
```python
23+
def postorderTraversal(root):
24+
ans = list()
25+
if not root:
26+
return ans
27+
28+
stack = []
29+
node = root
30+
prev = None
31+
while stack or node:
32+
while node:
33+
# 遍历左节点
34+
stack.append(node)
35+
node = node.left
36+
node = stack.pop()
37+
if not node.right or node.right == prev:
38+
# 根节点
39+
ans.append(node.val)
40+
prev = node
41+
node = None
42+
else:
43+
# 遍历右节点
44+
stack.append(node)
45+
node = node.right
46+
return ans
47+
```

‎leetcode_tree/二叉树的层序遍历.md‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
# 102.二叉树的层序遍历
2+
## 题目
3+
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
4+
5+
## 分析
6+
* 队列存放当前层所有节点
7+
* 每次拓展下一层的时候，需要将当前队列中所有节点都取出来进行拓展
8+
* 保证每次拓展完时候，队列中存放的都是同一层的所有节点
9+
* 用列表保存每层的元素值
10+
11+
```python
12+
from queue import Queue
13+
def levelOrder(root):
14+
ans = list()
15+
if not root:
16+
return ans
17+
q = Queue()
18+
q.put(root)
19+
while q.qsize():
20+
size = q.qsize()
21+
tmp = []
22+
for _ in range(size):
23+
# 取出这一层所有的元素
24+
node = q.get()
25+
if node:
26+
tmp.append(node.val)
27+
if node.left:
28+
q.put(node.left)
29+
if node.right:
30+
q.put(node.right)
31+
if tmp:
32+
ans.append(tmp)
33+
return ans
34+
```

‎leetcode_tree/反转二叉树.md‎

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
# 226.反转二叉树
2+
## 题目
3+
翻转一棵二叉树。
4+
```python
5+
输入
6+
4
7+
/ \
8+
2 7
9+
/ \ / \
10+
1 3 6 9
11+
12+
输出
13+
4
14+
/ \
15+
7 2
16+
/ \ / \
17+
9 6 3 1
18+
```
19+
20+
## 分析
21+
#### 递归
22+
* 新树的左子树，是旧树的右子树的反转树
23+
* 新树的右子树，是旧树的左子树的反转树
24+
25+
![](../pic/leetcode_tree/226_1.png)
26+
```python
27+
def invertTree(root):
28+
if not root:
29+
return root
30+
left = invertTree(root.right)
31+
right = invertTree(root.left)
32+
root.left = left
33+
root.right = right
34+
return root
35+
```
36+
37+
#### 迭代
38+
* 遍历所有节点，交换每个节点的左右节点的位置
39+
40+
![](../pic/leetcode_tree/226_1.gif)
41+
42+
```python
43+
def invertTree(root):
44+
if not root:
45+
return root
46+
q_ = [root]
47+
while q_:
48+
node = q_.pop()
49+
left = node.left
50+
right = node.right
51+
# 左右两个子节点交换
52+
node.left = right
53+
node.right = left
54+
if node.left:
55+
q_.append(node.left)
56+
if node.right:
57+
q_.append(node.right)
58+
return root
59+
```

‎pic/leetcode_tree/144_1.gif‎

207 KB
Loading

‎pic/leetcode_tree/226_1.gif‎

259 KB
Loading

‎pic/leetcode_tree/226_1.png‎

39 KB
Loading

‎pic/leetcode_tree/94_1.gif‎

153 KB
Loading

0 commit comments

Comments
 (0)