Skip to content

Commit 404faa2

Browse files
eadsteadst
authored
Update binary_tree.md
1 parent 6eca83a commit 404faa2

File tree

1 file changed

+225
-0
lines changed

1 file changed

+225
-0
lines changed

‎data_structure/binary_tree.md

Lines changed: 225 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -67,6 +67,36 @@ class Solution:
6767
return preorder
6868
```
6969

70+
```Python
71+
class Solution:
72+
def preorderTraversal(self, root: TreeNode) -> List[int]:
73+
if not root:
74+
return []
75+
result = []
76+
stock = []
77+
while root or stock:
78+
while root:
79+
result.append(root.val)
80+
stock.append(root)
81+
root = root.left
82+
root = stock.pop()
83+
root = root.right
84+
return result
85+
```
86+
87+
```Python
88+
class Solution:
89+
def preorderTraversal(self, root: TreeNode) -> List[int]:
90+
result = []
91+
def helper(root):
92+
if root:
93+
result.append(root.val)
94+
helper(root.left)
95+
helper(root.right)
96+
helper(root)
97+
return result
98+
```
99+
70100
#### [中序非递归](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/)
71101

72102
```Python
@@ -85,6 +115,28 @@ class Solution:
85115
return inorder
86116
```
87117

118+
```Python
119+
# Definition for a binary tree node.
120+
# class TreeNode:
121+
# def __init__(self, val=0, left=None, right=None):
122+
# self.val = val
123+
# self.left = left
124+
# self.right = right
125+
class Solution:
126+
def inorderTraversal(self, root: TreeNode) -> List[int]:
127+
result = []
128+
stack = []
129+
while root or stack:
130+
while root:
131+
stack.append(root)
132+
root = root.left
133+
root = stack.pop()
134+
result.append(root.val)
135+
root = root.right
136+
return result
137+
138+
```
139+
88140
#### [后序非递归](https://leetcode-cn.com/problems/binary-tree-postorder-traversal/)
89141

90142
```Python
@@ -110,6 +162,26 @@ class Solution:
110162
return postorder
111163
```
112164

165+
```Python
166+
class Solution:
167+
def postorderTraversal(self, root: TreeNode) -> List[int]:
168+
result = []
169+
stack = []
170+
visit = None
171+
while root or stack:
172+
while root:
173+
stack.append(root)
174+
root = root.left
175+
node = stack[-1]
176+
if not node.right or node.right == visit:
177+
result.append(node.val)
178+
visit = node
179+
stack.pop()
180+
else:
181+
root = node.right
182+
return result
183+
```
184+
113185
注意点
114186

115187
- 核心就是：根节点必须在右节点弹出之后，再弹出
@@ -161,6 +233,26 @@ class Solution:
161233
return levels
162234
```
163235

236+
```Python
237+
class Solution:
238+
def levelOrder(self, root: TreeNode) -> List[List[int]]:
239+
result = []
240+
if not root:
241+
return result
242+
stack = collections.deque([root])
243+
while stack:
244+
length = len(stack)
245+
result.append([])
246+
for _ in range(length):
247+
root = stack.popleft()
248+
result[-1].append(root.val)
249+
if root.left:
250+
stack.append(root.left)
251+
if root.right:
252+
stack.append(root.right)
253+
return result
254+
```
255+
164256
### 分治法应用
165257

166258
先分别处理局部，再合并结果
@@ -220,6 +312,25 @@ class Solution:
220312
return depth
221313
```
222314

315+
```Python
316+
class Solution:
317+
def maxDepth(self, root: TreeNode) -> int:
318+
level = 0
319+
if not root:
320+
return level
321+
stack = collections.deque([root])
322+
while stack:
323+
level += 1
324+
length = len(stack)
325+
for _ in range(length):
326+
root = stack.popleft()
327+
if root.left:
328+
stack.append(root.left)
329+
if root.right:
330+
stack.append(root.right)
331+
return level
332+
```
333+
223334
### [balanced-binary-tree](https://leetcode-cn.com/problems/balanced-binary-tree/)
224335

225336
> 给定一个二叉树，判断它是否是高度平衡的二叉树。
@@ -278,6 +389,22 @@ class Solution:
278389
return True
279390
```
280391

392+
```Python
393+
class Solution:
394+
def isBalanced(self, root: TreeNode) -> bool:
395+
result = [True]
396+
def helper(root):
397+
if not root:
398+
return 0
399+
left = helper(root.left)
400+
right = helper(root.right)
401+
if abs(left-right) > 1:
402+
result[-1] = False
403+
return max(left, right) + 1
404+
_ = helper(root)
405+
return result[-1]
406+
```
407+
281408
### [binary-tree-maximum-path-sum](https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/)
282409

283410
> 给定一个**非空**二叉树，返回其最大路径和。
@@ -305,6 +432,22 @@ class Solution:
305432
return self.maxPath
306433
```
307434

435+
```Python
436+
class Solution:
437+
def maxPathSum(self, root: TreeNode) -> int:
438+
self.maxPath = float("-inf")
439+
def helper(root):
440+
if not root:
441+
return float("-inf")
442+
left = helper(root.left)
443+
right = helper(root.right)
444+
curPath = max(left, 0) + max(right, 0) + root.val
445+
self.maxPath = max(self.maxPath, curPath, left, right)
446+
return max(left, right, 0) + root.val
447+
helper(root)
448+
return self.maxPath
449+
```
450+
308451
### [lowest-common-ancestor-of-a-binary-tree](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)
309452

310453
> 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
@@ -334,6 +477,22 @@ class Solution:
334477
return None
335478
```
336479

480+
```Python
481+
class Solution:
482+
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
483+
if root == p or root == q or not root:
484+
return root
485+
left = self.lowestCommonAncestor(root.left, p, q)
486+
right = self.lowestCommonAncestor(root.right, p, q)
487+
if left and right:
488+
return root
489+
if left:
490+
return left
491+
if right:
492+
return right
493+
return None
494+
```
495+
337496
### BFS 层次应用
338497

339498
### [binary-tree-zigzag-level-order-traversal](https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/)
@@ -380,6 +539,33 @@ class Solution:
380539
return levels
381540
```
382541

542+
```Python
543+
class Solution:
544+
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
545+
result = []
546+
if not root:
547+
return result
548+
order = 1
549+
stack = collections.deque([root])
550+
while stack:
551+
length = len(stack)
552+
temp = []
553+
for _ in range(length):
554+
root = stack.popleft()
555+
temp.append(root.val)
556+
if root.left:
557+
stack.append(root.left)
558+
if root.right:
559+
stack.append(root.right)
560+
if order:
561+
result.append(temp)
562+
order = 0
563+
else:
564+
result.append(temp[::-1])
565+
order = 1
566+
return result
567+
```
568+
383569
### 二叉搜索树应用
384570

385571
### [validate-binary-search-tree](https://leetcode-cn.com/problems/validate-binary-search-tree/)
@@ -440,6 +626,25 @@ class Solution:
440626
return True
441627
```
442628

629+
```Python
630+
class Solution:
631+
def isValidBST(self, root: TreeNode) -> bool:
632+
if not root:
633+
return True
634+
pre = float("-inf")
635+
stack = []
636+
while root or stack:
637+
while root:
638+
stack.append(root)
639+
root = root.left
640+
root = stack.pop()
641+
if pre >= root.val:
642+
return False
643+
pre = root.val
644+
root = root.right
645+
return True
646+
```
647+
443648
#### [insert-into-a-binary-search-tree](https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/)
444649

445650
> 给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。
@@ -469,6 +674,26 @@ class Solution:
469674
node = node.left
470675
```
471676

677+
```Python
678+
class Solution:
679+
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
680+
if not root:
681+
return TreeNode(val)
682+
node = root
683+
while 1:
684+
if val > root.val:
685+
if root.right:
686+
root = root.right
687+
else:
688+
root.right = TreeNode(val)
689+
return node
690+
else:
691+
if root.left:
692+
root = root.left
693+
else:
694+
root.left = TreeNode(val)
695+
return node
696+
```
472697
## 总结
473698

474699
- 掌握二叉树递归与非递归遍历

0 commit comments

Comments
 (0)