---
# System prepended metadata

title: '**程式筆記(binary tree)**'
tags: [code, binary tree, note]

---

# **程式筆記(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 | 
| -------- | -------- | 
|![](https://hackmd.io/_uploads/HyMmTJ5Hh.png) | ![](https://hackmd.io/_uploads/HkwY21cB2.png)     | 


| 直接返回5，因為一邊有東西一邊沒東西 | 兩邊有東西就返回節點3 | 
| -------- | -------- | 
|![](https://hackmd.io/_uploads/rJ_FaycS3.png)  | ![](https://hackmd.io/_uploads/rkFhak9Sn.png) | 


```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
![](https://hackmd.io/_uploads/H1wtCSiB2.png)

* **樹的遞迴撇步**
return遞迴的東西，可以想成是在樹枝上傳遞，而且是return回"上面"的樹枝先從最尾端(也就是leaf)開始思考，
忽略遞歸呼叫的那幾行，只關注它的上方與下方，上代表待操作的東西，可能是要做某些操作(或是單純return)，做完依照遞歸下方的區域return參數
可以把它分解為123步，詳見[這裡](https://www.youtube.com/watch?v=wDsFfgv4OGY)




---

**:star2:** binary tree traversal

preorder - 前序 -> 中 -> 左 -> 右
inorder - 中序 -> 左 -> 中 -> 右
postorder - 後序 -> 左 -> 右 -> 中
![](https://hackmd.io/_uploads/B1G_WWoHn.png =70%x)

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
看樹葉是否相同
![image](https://hackmd.io/_uploads/r1nZFjE6R.png =60%x)
```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() 函數應用在元組的列表或元組時，它預設會根據每個元組的第一個元素進行排序。如果第一個元素相同，則會考慮第二個元素
![image](https://hackmd.io/_uploads/B1dCtAj3p.png =70%x)

```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(後面那次單獨拉出來看)
![image](https://hackmd.io/_uploads/B1QZjwAh0.png =30%x)

```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

![image](https://hackmd.io/_uploads/rJArkVdJyl.png =50%x)

```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`