# **程式筆記(binary tree)**
:::info
:information_source: 日期 : 2023/05/23
:::
**:star2:** binary tree 基本
* Invert反轉
```python
def invert(self, node):
if not node:
return
node.left, node.right = node.right, node.left
self.invertTree(node.left)
self.invertTree(node.right)
return node
```
* Depth找高度
可以用bfs(用q)，也可以用遞歸，leaf從0開始算，height = max(left, right) + 1
```python
def find_height(node):
if not node:
return 0
l_h = find_height(node.left)
r_h = find_height(node.right)
return max(l_h, r_h) + 1
```
* 找diameter
這個樹上任兩個node之間的最長距離(算edge)
最長的某一條即使不會經過tree root，也必定會經過某一個node，在那時候就會把最大值結果存下來，所以只要對每個node算它左右兩邊leaf相加的最大值即可
```python
def findLength(self, node):
if not node:
return 0
right = self.findLength(node.right)
left = self.findLength(node.left)
# 以這個node為出發點 把它的left right加起來
self.res = max(left + right, self.res)
return max(left, right) + 1
```
* 是否height-balanced
如果left right相差1以上即不平衡，也是靠找高度 + 設定全域一個boolean去紀錄
如果問是否鏡像平衡，會發現來回檢查(左樹的右枝 vs 右樹的左枝)是否相同，也是用檢查兩樹是否相同的if三原則去看
```python
def findHeight(self, node):
if not node:
return 0
left = self.findHeight(node.left)
right = self.findHeight(node.right)
if abs(left - right) > 1:
self.boolean = False
return max(left, right) + 1
```
* 是否same
三個比較方式
```python
def isSameTree(self, q, p):
if not q and not p:
return True
if not q or not p:
return False
# 要注意這裡不能比較數字True
# 不然False會抓不出來
if q.val != p.val:
return False
return (self.isSameTree(q.left, p.left) and self.isSameTree(q.right, p.right))
```
* 是否和subtree相同
主函式檢查是否為相同樹，如果不是，則遞迴檢查其左右樹，以左樹或右樹為root。isSubtree的self.sameTree呼叫，可以想像是base case，只要有一為True，則回傳True
```python
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
if not root:
return False
if self.sameTree(root, subRoot):
return True
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
```
* Lowest Common Ancestor of a Binary Tree
找最小共同祖先
如果找到題目給訂的node，用樹枝去傳node
如果只有單邊有node，那就傳單邊node，如果雙邊都有，那就傳它們的parent node
| 當左(右)邊有東西，右(左)邊沒有東西，則返回有東西那一邊的數值 | 兩邊有東西就返回節點2 |
| -------- | -------- |
| |  |
| 直接返回5，因為一邊有東西一邊沒東西 | 兩邊有東西就返回節點3 |
| -------- | -------- |
| |  |
```python
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def traverse(node):
if not node:
return None
if node == p or node == q:
return node
l = traverse(node.left)
r = traverse(node.right)
if l and r:
return node
elif l:
return l
elif r:
return r
else:
return None
return traverse(root)
```
* 層Level Order Traversal
若是要一層一層儲存node，可以用bfs的queue + popleft
* 節點編號規則
左子樹是父節點編號乘以2
右子樹是父節點編號乘以2加1
* **樹的遞迴撇步**
return遞迴的東西，可以想成是在樹枝上傳遞，而且是return回"上面"的樹枝先從最尾端(也就是leaf)開始思考，
忽略遞歸呼叫的那幾行，只關注它的上方與下方，上代表待操作的東西，可能是要做某些操作(或是單純return)，做完依照遞歸下方的區域return參數
可以把它分解為123步，詳見[這裡](https://www.youtube.com/watch?v=wDsFfgv4OGY)
---
**:star2:** binary tree traversal
preorder - 前序 -> 中 -> 左 -> 右
inorder - 中序 -> 左 -> 中 -> 右
postorder - 後序 -> 左 -> 右 -> 中
inorder
```python
def traverse(self, node, res):
if not node:
return
self.traverse(node.left, res)
res.append(node.val)
self.traverse(node.right, res)
```
preorder
```python
res.append(node.val)
left = dfs(node.left)
right = dfs(node.right)
```
preorder轉成tree
```python
root = TreeNode(res[self.i])
self.i += 1
root.left = dfs_()
root.right = dfs_()
ps. self.i是用來控制index
```
* 重組tree(inorder和preorder)
步驟 : 一開始先抓住preorder[0]，在去inorder抓preorder[0]的index，分辨left和right
每個node都會有當到root的機會，會先處理最左邊的那個node，並把結果回傳給上一層的root.left
```python
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
return self.reconstruct(preorder, inorder)
def reconstruct(self, preorder, inorder):
if not preorder or not inorder:
return None
root = preorder[0]
i = inorder.index(root)
left = self.reconstruct(preorder[1:i + 1], inorder[:i])
right = self.reconstruct(preorder[i + 1:], inorder[i + 1:])
return TreeNode(root, left, right)
```
* 重組tree(inorder和postorder)
知道中序 + 任意一個順序，即可以得出這個tree
用差不多的思路，以postorder[-1]是root
```python
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
return self.helper(inorder, postorder)
def helper(self, inorder, postorder):
if not inorder and not postorder:
return None
root_val = postorder[-1]
index = inorder.index(root_val)
root = TreeNode(root_val)
root.left = self.helper(inorder[:index], postorder[:index])
root.right = self.helper(inorder[index + 1:], postorder[index:-1])
return root
```
---
**:star2:** binary tree 基礎2
* Binary Tree Maximum Path Sum累加數值最大
每次都回傳root + max(left, right)，也就是只選中 + 左或中 + 右，在計算過程中也可以順便更新中 + 左 + 右
特別留意的是，如果左右為負的話，可以直接只選**中**(因為不管選哪個，都會使sum變得更小)(也就是0)
```python
left = max(self.dfs(node.left), 0)
right = max(self.dfs(node.right), 0)
self.res = max(self.res, node.val + left + right)
return node.val + max(left, right)
```
* Flip Equivalent Binary Trees
看翻轉的tree是否相等
用兩個條件去把關，有一個回傳true就是true
```python
class Solution:
def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
def isValid(node1, node2):
if not node1 and not node2:
return True
if not node1 or not node2:
return False
if node1.val != node2.val:
return False
return (isValid(node1.right, node2.right) and isValid(node1.left, node2.left)) or (isValid(node1.right, node2.left) and isValid(node1.left, node2.right))
return isValid(root1, root2)
```
* Leaf-Similar Trees
看樹葉是否相同
```python
class Solution:
def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
if not root1 or not root2:
return []
res1, res2 = [], []
def traverse(node, res):
if not node.left and not node.right:
res.append(node.val)
return
if node.left: # 還是要檢查，以防單邊樹
traverse(node.left, res)
if node.right:
traverse(node.right, res)
traverse(root1, res1)
traverse(root2, res2)
return res1 == res2
```
* Minimum Depth of Binary Tree
兩邊都是null的才算葉，才能開始計算高度。如果某一node一邊null一邊有葉，那只需計算有葉那邊。如果兩邊有葉，則回傳最小的高度
```python
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
return self.findDepth(root)
def findDepth(self, node):
if not node:
return 0
if not node.left:
return self.findDepth(node.right) + 1
elif not node.right:
return self.findDepth(node.left) + 1
else: # have node.left and node.right
return min(self.findDepth(node.left), self.findDepth(node.right)) + 1
```
* Count Good Nodes in Binary Tree
如果新遍歷的node比任何路徑上的node都還大的話，則res加1
```python
class Solution:
def goodNodes(self, root: TreeNode) -> int:
if not root:
return 0
self.res = 0
def traverse(node, maxN):
if not node:
return
if node.val >= maxN:
self.res += 1
maxN = node.val
if node.left:
traverse(node.left, maxN)
if node.right:
traverse(node.right, maxN)
traverse(root, float("-inf"))
return self.res
```
* Vertical Order Traversal of a Binary Tree
因為最後要依照每一個col輸出，所以先用col為key方便sorted(values.keys())，然後依照規則去traverse每一個node
然後再依照每個row去輸出，也是需要sort
sorted() 函數應用在元組的列表或元組時，它預設會根據每個元組的第一個元素進行排序。如果第一個元素相同，則會考慮第二個元素
```python
class Solution:
def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
values = collections.defaultdict(list)
result = []
self.verticalOrder(root, 0, 0, values)
# sorted 保留原列表
for c in sorted(values.keys()):
temp = []
for r, val in sorted(values[c]):
temp.append(val)
result.append(temp)
return result
def verticalOrder(self, root, r, c, values):
if not root:
return
values[c].append((r, root.val))
self.verticalOrder(root.left, r + 1, c - 1, values)
self.verticalOrder(root.right, r + 1, c + 1, values)
```
* graph
如果要把binary tree建立成無向graph形式，也是建立一個parent和child的dict，循環呼叫
---
**:star2:** binary tree ZigZag
* Binary Tree Zigzag Level Order Traversal
第一層由左到右遍歷，第二層由又到左遍歷，用depth這個變數去追蹤
```python
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return None
res = []
q = deque()
q.append(root)
depth = 1
while q:
temp_res = []
for _ in range(len(q)):
node = q.popleft()
temp_res.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
if depth % 2:
res.append(temp_res)
else:
res.append(temp_res[::-1])
depth += 1
return res
```
* Longest ZigZag Path in a Binary Tree
一樣走traverse，沿路一直蒐集step，如果連續往同一個方向走2次，那只能算1(後面那次單獨拉出來看)
```python
class Solution:
def __init__(self):
self.res = 0
def longestZigZag(self, root: Optional[TreeNode]) -> int:
def traverse(node, iden, step):
# iden = True = previous is left
# step = how many path you go through
if not node:
return
self.res = max(self.res, step)
if node.left:
if iden:
traverse(node.left, True, 1)
else:
traverse(node.left, True, step + 1)
if node.right:
if iden:
traverse(node.right, False, step + 1)
else:
traverse(node.right, False, 1)
if root:
traverse(root.left, True, 1)
traverse(root.right, False, 1)
return self.res
```
---
**:star2:** 進階遞迴
* Flatten Binary Tree to Linked List
```python
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
self.reconnect(root)
def reconnect(self, node):
if not node:
return None
if not node.left and not node.right:
return node
left_tail = self.reconnect(node.left)
right_tail = self.reconnect(node.right)
if left_tail:
left_tail.right = node.right # 左尾接到右頭
node.right = node.left # 右頭改成左頭
node.left = None # 左頭指向空
return right_tail if right_tail else left_tail
```
---
**:star2:** path sum系列
* Path Sum
必為root-to-leaf，回傳true/false
```python
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
return self.traverse(root, targetSum, 0)
def traverse(self, node, targetSum, total):
if not node:
return False
total += node.val
if not node.left and not node.right and total == targetSum:
return True
return (self.traverse(node.left, targetSum, total) or self.traverse(node.right, targetSum, total))
```
* Path Sum II
必為root-to-leaf，回傳路徑
最後要把path pop掉，不能用remove，否則有相同數字在path裡就會錯誤
```python
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
if not root:
return []
self.res = []
self.traverse(root, targetSum, 0, [])
return self.res
def traverse(self, node, targetSum, total, path):
if not node:
return
total += node.val
path.append(node.val)
if not node.left and not node.right and total == targetSum:
self.res.append(path.copy())
self.traverse(node.left, targetSum, total, path + [node.val])
self.traverse(node.right, targetSum, total, path + [node.val])
path.pop()
```
* Path Sum III
不一定要root也不一定要leaf
注意幾點:
* dict把0:1加入，考慮root到leaf即為正解
* dict為sum:count
* 需要先check，再把自己加進去，否則會考慮到自己，如果targetSum為0，那任何 (自己-自己) 都會成立
* 最後把左右子樹檢查完了，需要去除root在dict的紀錄，因為要往上跑其他大子樹
```python
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
record = defaultdict(int)
record[0] = 1
self.res = 0
self.traverse(root, targetSum, 0, record)
return self.res
def traverse(self, node, targetSum, total, record):
if not node:
return
total += node.val
if (total - targetSum) in record.keys():
self.res += record[total - targetSum]
record[total] += 1
self.traverse(node.left, targetSum, total, record)
self.traverse(node.right, targetSum, total, record)
record[total] -= 1
```
---
---
**講解連結**
Provided by. me
###### tags: `binary tree` `note` `code`
Sign in with Wallet
Connect another wallet