---
# System prepended metadata

title: Tree (15)
tags: [working]

---

# Tree (15)

> 紀錄 NeetCode-150 與 LeetCode 的解題想法、刷題過程與錯誤，以 Python 或 C++ 兩種語言為主
> 
> 其他 NeetCode-150 或 LeetCode 的主題請見 [Here](https://hackmd.io/-ovTFlzLRWaSgzDGhbSwsA)

<!-- 常用色碼紀錄
Easy:   <font color="#00ad5f">**Easy**</font>
Medium: <font color="#ffbb00">**Medium**</font>
Hard:   <font color="#ee2f56">**Hard**</font>
-->

## 1. Invert Binary Tree
<font color="#00ad5f">**Easy**</font>

> You are given the root of a binary tree `root`. Invert the binary tree and return its root.

### Example 1:

![image](https://hackmd.io/_uploads/BJFgh7JrJl.png)

```java
Input: root = [1,2,3,4,5,6,7]

Output: [1,3,2,7,6,5,4]
```

### Example 2:

![image](https://hackmd.io/_uploads/B16G37krye.png)

```java
Input: root = [3,2,1]

Output: [3,1,2]
```

### Example 3:
```java
Input: root = []

Output: []
```

### Constraints

* `0 <= The number of nodes in the tree <= 100`
* `-100 <= Node.val <= 100`

### Recommended complexity

* Time complexity:　$O(n)$
* Space complexity: $O(n)$

### Solution
從題幹可以發現每個節點的 sub-tree 都做了交換。所以可以走訪每個節點，每經過一個節點就交換該節點左右子樹的位置。

第一種方法是採用 pre-order traversal 的方式走訪每個節點，且將走訪的函式分離出來額外實作。
```python=
# 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]:
        self.preOrderTraversal(root)

        return root


    def preOrderTraversal(self, node):
        if node:
            self.swap(node)
            self.preOrderTraversal(node.left)
            self.preOrderTraversal(node.right)

    def swap(self, node):
        temp = node.left
        node.left = node.right
        node.right = temp

        return node
```

第二種方法也是採用 pre-order traversal 的方式走訪每個節點，但將走訪的過程實作在建構函式中。

```python=
# more simple ver.
# 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 root:
            temp = root.left
            root.left = root.right
            root.right = temp

            # also use self.swap(root)

            self.invertTree(root.left)
            self.invertTree(root.right)
        
        return root

    # def swap(self, node):
    #     tmp = node.left
    #     node.left = node.right
    #     node.right = node.left
```

## 2. Maximum Depth of Binary Tree
<font color="#00ad5f">**Easy**</font>

> Given the `root` of a binary tree, return its depth.
>
> The **depth** of a binary tree is defined as the number of nodes along the longest path from the root node down to the farthest leaf node.

### Example 1:
<img src="https://imagedelivery.net/CLfkmk9Wzy8_9HRyug4EVA/5ea6da77-7e43-43e0-dd9d-e879ca0b1600/public" height=300>

```java
Input: root = [1,2,3,null,null,4]

Output: 3
```

### Example 2:
```java
Input: root = []

Output: 0
```

### Constraints

* `0 <= The number of nodes in the tree <= 100`
* `-100 <= Node.val <= 100`

### Recommended complexity

* Time complexity: $O(n)$
* Space complexity: $O(n)$

### Solution

考慮每個 sub-tree 的深度。每進入一個節點就預設該層的深度為 1。每個節點的實際深度會依據左右子數來決定。比較左右子樹的深度後選擇較深的那個，再加上節點本身的深度(1)，才會是該節點真正的深度。

#### 1. Recursion

遞迴版本預設葉節點的深度為 1，往上的同時逐層增加深度。
```python=
# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        currDepth = 0

        if root:
            currDepth += 1
            
            leftDepth = self.maxDepth(root.left)
            rightDepth = self.maxDepth(root.right)
            currDepth += max(leftDepth, rightDepth)
            # if leftDepth >= rightDepth:
            #     currDepth += leftDepth
            # else:
            #     currDepth += rightDepth
        
        return currDepth
```

#### 2. Iteration
迭代的方式是使用 stack 進行，要注意的是 stack 彈出來(pop)的順序對應著 traversal 的順序，所以壓入(push)的順序要跟 traversal 的順序顛倒。

每進入(push)一個節點就計算該節點的深度(depth + 1)，彈出(pop)時再比較該節點的深度與當前計算的深度(res)

需要注意的是，比較的動作(`res = max(res, depth)`)要放在 `if` 結構內部。如果放在 `if` 之前，那 pop 出來如果的節點剛好是 NULL，就會改變 depth 的值，使得最後的 depth 變大。

迭代版本預設根節點的深度為 1，與遞迴版本相反，往下的同時逐層增加深度。

```python=
# stack ver.
# stack 彈出來的順序對應 traversal 的順序
# 所以壓入的順序跟 traversal 的順序顛倒
# 每進到一個節點就計算該節點的深度
# 彈出的同時比較該節點與當前計算的深度
# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        stack = [[root, 1]]
        res = 0

        while stack:
            node, depth = stack.pop()

            if node:
                res = max(res, depth)
                stack.append([node.right, depth + 1])
                stack.append([node.left, depth + 1])
        return res
```

## 3. Diameter of Binary Tree
<font color="#00ad5f">**Easy**</font>

> The **diameter** of a binary tree is defined as the **length** of the longest path between *any two nodes within the **tree***. The path does not necessarily have to pass through the root.
>
> The **length** of a path between two nodes in a binary tree is the number of edges between the nodes.
>
> Given the root of a binary tree `root`, return the **diameter** of the tree.

### Example 1:

<img src="https://imagedelivery.net/CLfkmk9Wzy8_9HRyug4EVA/90e1d7a0-4322-4c5d-c59b-dde2bf92bb00/public" height=300>

```java
Input: root = [1,null,2,3,4,5]

Output: 3
```
Explanation: 3 is the length of the path [1,2,3,5] or [5,3,2,4].

### Example 2:

```java
Input: root = [1,2,3]

Output: 2
```

### Constraints

* `1 <= number of nodes in the tree <= 100`
* `-100 <= Node.val <= 100`

### Recommended complexity

* Time complexity: $O(n)$
* Space complexity: $O(n)$

### Solution

對於任意節點而言，通過它的最大路徑長 = 左子數的高度 + 右子樹的高度。所以類似前一題的做法去計算樹的高度。

不同的是，這次每計算完一個節點的高度後，需要去計算通過它的路徑長並與其他路徑長做比較。因此會需要一個全域變數(`self.diameter`)來儲存目前最長的路徑。

```python=
# 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 diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:

        self.diameter = 0
        self.postOrderTraversal(root)
        return self.diameter

        
    
    def postOrderTraversal(self, node):
        currDepth = 0

        if node:
            currDepth += 1

            leftDepth = self.postOrderTraversal(node.left)
            rightDepth = self.postOrderTraversal(node.right)
            currDepth += max(leftDepth, rightDepth)

            self.diameter = max(self.diameter, leftDepth + rightDepth)

        return currDepth
```

## 4. Balanced Binary Tree
<font color="#00ad5f">**Easy**</font>

> Given a binary tree, return `true` if it is height-balanced and `false` otherwise.
>
> A **height-balanced** binary tree is defined as a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

### Example 1:

![image](https://hackmd.io/_uploads/rkyuiKgr1x.png)

```java
Input: root = [1,2,3,null,null,4]

Output: true
```

### Example 2:

![image](https://hackmd.io/_uploads/S1e9itgByx.png)

```java
Input: root = [1,2,3,null,null,4,null,5]

Output: false
```

### Example 3:
```java
Input: root = []

Output: true
```
### Constraints

* The number of nodes in the tree is in the range `[0, 1000]`
* `-1000 <= Node.val <= 1000`

### Recommended complexity

* Time complexity: $O(n)$
* Space complexity: $O(n)$

### Solution

仿照計算樹高的方式。因為每個節點都需要接收下層回傳的高度，所以計算高度時可以同時計算「以該節點為根結點時，左右子樹是否平衡(`abs(leftDepth - rightDepth) > 1`)」，並將結果用一個全域變數儲存。

```python=
# 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 isBalanced(self, root: Optional[TreeNode]) -> bool:
        self.res = True

        self.postOrderTraversal(root)
        
        return self.res

    def postOrderTraversal(self, node):
        currDepth = 0

        if node:
            currDepth += 1
            leftDepth = self.postOrderTraversal(node.left)
            rightDepth = self.postOrderTraversal(node.right)
            currDepth += max(leftDepth, rightDepth)

            if abs(leftDepth - rightDepth) > 1:
                self.res = False
        return currDepth
```

## 5. Same Tree
<font color="#00ad5f">**Easy**</font>

> Given the roots of two binary trees `p` and `q`, return `true` if the trees are **equivalent**, otherwise return `false`.
>
> Two binary trees are considered **equivalent** if they share the exact same structure and the nodes have the same values.

### Example 1:

![image](https://hackmd.io/_uploads/r1SN6YeB1l.png)

```java
Input: p = [1,2,3], q = [1,2,3]

Output: true
```

### Example 2:

![image](https://hackmd.io/_uploads/BkvrpKxH1g.png)

```java
Input: p = [4,7], q = [4,null,7]

Output: false
```

### Example 3:

![image](https://hackmd.io/_uploads/Sk9I6FgBJe.png)

```java
Input: p = [1,2,3], q = [1,3,2]

Output: false
```

### Constraints

* `0 <= The number of nodes in both trees <= 100`
* `-100 <= Node.val <= 100`

### Recommended complexity

* Time complexity: $O(n)$
* Space complexity: $O(n)$

### Solution

同樣走訪樹的每個節點，每進入一個節點時就判斷該兩棵樹的對應節點的值是否相同。

* 當兩棵樹的對應節點都非空且數值相同
    * 繼續往左子樹或右子樹走訪
* 當持續走到兩棵樹的某個對應節點都是空的，表示該子樹是等價的

```python=
# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        
        if (not p) and (not q):
            return True

        if p and q and p.val == q.val:    
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        else:
            return False
```

## 6. Subtree of Another Tree
<font color="#00ad5f">**Easy**</font>

> Given the roots of two binary trees `root` and `subRoot`, return `true` if there is a subtree of `root` with the same structure and node values of `subRoot` and `false` otherwise.
>
> A subtree of a binary tree `tree` is a tree that consists of a node in `tree` and all of this node's descendants. The tree `tree` could also be considered as a subtree of itself.

### Example 1:
![image](https://hackmd.io/_uploads/Bk3MkcgHkl.png)

```java
Input: root = [1,2,3,4,5], subRoot = [2,4,5]

Output: true
```

### Example 2:
![image](https://hackmd.io/_uploads/Bkm4kqlrJe.png)

```java
Input: root = [1,2,3,4,5,null,null,6], subRoot = [2,4,5]

Output: false
```

### Constraints

* `0 <= The number of nodes in both trees <= 100`
* `-100 <= root.val, subRoot.val <= 100`

### Recommended complexity

* Time complexity: better than $O(m \cdot n)$
* Space complexity: better than $O(m + n)$

### Solution

要比較 subRoot 是否包含在 root 中，所以要去檢查 root 中有沒有 subRoot 的等價結構。每走訪到 root 的其中一個節點，就去執行前一題所說的函式(`isSameTree`)，判斷該節點的子樹與 subRoot 是否相同。

* 相同，返回 `True`
* 不同，繼續搜尋左右子樹

```python=
# 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 isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if not subRoot:
            return True
        if not root:
            return False

        if self.sameTree(root, subRoot):
            return True
        else:
            return (self.isSubtree(root.left, subRoot) or
                    self.isSubtree(root.right, subRoot))
        
    def sameTree(self, root, subRoot):
        if (not root) and (not subRoot):
            return True
        
        if root and subRoot and root.val == subRoot.val:
            return (self.sameTree(root.left, subRoot.left) and
                    self.sameTree(root.right, subRoot.right))
        else:
            return False
```

## 7. Lowest Common Ancestor of A Binary Search Tree
<font color="#ffbb00">**Medium**</font>

> Given a binary search tree (BST) where all node values are *unique*, and two nodes from the tree `p` and `q`, return the lowest common ancestor (LCA) of the two nodes.
>
> The lowest common ancestor between two nodes `p` and `q` is the lowest node in a tree `T` such that both `p` and `q` as descendants. The ancestor is allowed to be a descendant of itself.

### Example 1:
![image](https://hackmd.io/_uploads/HJ_hsWVBkx.png)

```java
Input: root = [5,3,8,1,4,7,9,null,2], p = 3, q = 8

Output: 5
```

### Example 2:
![image](https://hackmd.io/_uploads/H1saj-VHJx.png)

```java
Input: root = [5,3,8,1,4,7,9,null,2], p = 3, q = 4

Output: 3
```
Explanation: The LCA of nodes 3 and 4 is 3, since a node can be a descendant of itself.

### Constraints

* `2 <= The number of nodes in the tree <= 100`
* `-100 <= Node.val <= 100`
* `p != q`
* `p` and `q` will both exist in the BST

### Recommended complexity

* Time complexity: $O(n)$
* Space complexity: $O(n)$

### Solution

至少要先找到給定的 p 與 q 才能知道他們的共同祖先。在走訪 binary search tree 的過程中：

* 若 p 與 q 都小於 root，往左子樹搜尋
* 若 p 與 q 都大於 root，往右子樹搜尋
* 若其中一個小於 root，另一個大於 root，則分開搜尋
    * 且該節點必為 p 與 q 的共同最小祖先(lowest common ancestor)
    * 且此情況也包含了 p 與 q 其中一個是 ancestor，因為這也算是一種分開搜尋

#### 1. Recursion
```python=
# recursion
# 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 lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        
        if max(p.val, q.val) < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        elif min(p.val, q.val) > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root
```

#### 2. Iteration
```python=
# iteration
# 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 lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        
        while root:
            if max(p.val, q.val) < root.val:
                root = root.left
            elif min(p.val, q.val) > root.val:
                root = root.right
            else:
                return root
        return root
```

## 8. Binary Tree Level Order Traversal
<font color="#ffbb00">**Medium**</font>

> Given a binary tree `root`, return the level order traversal of it as a nested list, where each sublist contains the values of nodes at a particular level in the tree, from left to right.

### Example 1:
![image](https://hackmd.io/_uploads/ryO7CbErJg.png)

```java
Input: root = [1,2,3,4,5,6,7]

Output: [[1],[2,3],[4,5,6,7]]
```

### Example 2:
```java
Input: root = [1]

Output: [[1]]
```

### Example 3:
```java
Input: root = []

Output: []
```

### Constraints

* `0 <= The number of nodes in both trees <= 1000`
* `-1000 <= Node.val <= 1000`

### Recommended complexity

* Time complexity: $O(n)$
* Space complexity: $O(n)$

### Solution

:::info
Level Order Traversal 必須使用 double queue 進行，Python 版本參考 [GeekforGeek](https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/?ref=gcse_outind#level-order-traversal)
:::

因為相同 level 要放同一個 sublist，所以每次開始走訪時前要先確定該層有多少個節點，不能取超過。同層的節點放同一個 sublist，該層做完後再放入最後的輸出串列中。

```python=
# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []

        if not root:
            return res
        
        queue = collections.deque([root])

        while queue:
            val = []
            queueLen = len(queue)
            
            for i in range(queueLen):
                node = queue.popleft()
                val.append(node.val)

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(val)
        return res
```

## 9. Binary Tree Right Side View
<font color="#ffbb00">**Medium**</font>

> You are given the `root` of a binary tree. Return only the values of the nodes that are visible from the right side of the tree, ordered from top to bottom.

### Example 1:
![image](https://hackmd.io/_uploads/BkUexM4Byl.png)

```java
Input: root = [1,2,3]

Output: [1,3]
```

### Example 2:
```java
Input: root = [1,2,3,4,5,6,7]

Output: [1,3,7]
```

### Constraints

* `0 <= number of nodes in the tree <= 100`
* `-100 <= Node.val <= 100`

### Recommended complexity

* Time complexity: $O(n)$
* Space complexity: $O(n)$

### Solution

類似前一題用 level order traversal 並在每層走訪前紀錄該層的節點數，走到最後一層再存值即可。

```python=
# 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 rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        
        if not root:
            return res
        
        queue = collections.deque([root])
        while queue:
            queueLen = len(queue)
            for i in range(queueLen):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                
                # find the rightmost node
                if (i + 1) == queueLen:
                    res.append(node.val)
        return res
```

## 10. Count Good Nodes in Binary Tree
<font color="#ffbb00">**Medium**</font>

> Within a binary tree, a node `x` is considered good if the path from the root of the tree to the node `x` contains no nodes with a value greater than the value of node `x`
>
> Given the root of a binary tree `root`, return the number of **good** nodes within the tree.

### Example 1:

<img src="https://imagedelivery.net/CLfkmk9Wzy8_9HRyug4EVA/9bf374f1-71fe-469e-2840-5d223d9d1b00/public" width=600>
```java
Input: root = [2,1,1,3,null,1,5]

Output: 3
```

### Example 2:
<img src="https://imagedelivery.net/CLfkmk9Wzy8_9HRyug4EVA/8df65da7-abac-4948-9a92-0bc7a8dda100/public">
```java
Input: root = [1,2,-1,3,4]

Output: 4
```

### Constraints

* `1 <= number of nodes in the tree <= 100`
* `-100 <= Node.val <= 100`

### Recommended complexity

* Time complexity: $O(n)$
* Space complexity: $O(n)$

### Solution

* 仿照一般樹的走訪往下搜尋
* 儲存路徑中的最大值，只要最大值被換掉，那該節點就是其中一個 good node
* 需要時刻追蹤每個節點當時的最大值(類似追蹤深度)，才能在返回上層時找到當時的最大值
* 因為節點 = 最大值時(`node.val >= maxValue`)也會是一個 good node，所以預設 `res = 0` 才能把根節點也算進去

```python=
# 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 goodNodes(self, root: TreeNode) -> int:
        res = 0
        maxValue = root.val
        stack = [(root, maxValue)]

        while stack:
            node, maxValue = stack.pop()
            if node.val >= maxValue:
                res += 1
                maxValue = node.val
            
            if node.right:
                stack.append((node.right, maxValue))
            if node.left:
                stack.append((node.left, maxValue))
        return res
```

## 11. Validate Binary Search Tree
<font color="#ffbb00">**Medium**</font>

> Given the `root` of a binary tree, return `true` if it is a **valid binary search tree**, otherwise return `false`.
>
> A v**alid binary search tree** satisfies the following constraints:
>
> * The left subtree of every node contains only nodes with keys **less than** the node's key.
> * The right subtree of every node contains only nodes with keys **greater than** the node's key.
> * Both the left and right subtrees are also binary search trees.

:::info
**勿混淆**
Binary search tree 指的是左/右子樹的**所有**節點都要小/大於根節點，且左右子樹也都是一個 binary search tree。因此深度越深的樹，最左/右邊節點的值會越來越小/大。
:::

### Example 1:
<img src="https://imagedelivery.net/CLfkmk9Wzy8_9HRyug4EVA/18f9a316-8dc2-4e11-d304-51204454ac00/public">

```java
Input: root = [2,1,3]

Output: true
```

### Example 2:
<img src="https://imagedelivery.net/CLfkmk9Wzy8_9HRyug4EVA/6f14cb8d-efad-4221-2beb-fba2b19c8a00/public">

```java
Input: root = [1,2,3]

Output: false
```

### Constraints

* `1 <= The number of nodes in the tree <= 1000`
* `-1000 <= Node.val <= 1000`

### Recommended complexity

* Time complexity: $O(n)$
* Space complexity: $O(n)$

### Solution

制定一個範圍 $[-\infty, \infty]$，每往下搜索一層就更新範圍的邊界值

* 往左子樹搜尋時
因為左子樹的所有節點都必須 < 根節點，所以範圍的上限更新成該左節點的值 $[-\infty, \text{leftNode}]$，表示往下的節點不能大於它

* 往右子樹搜尋時
因為右子樹的所有節點都必須 > 根節點，所以範圍的下限必須更新成該節點值 $[\text{rightNode}, \infty]$，表示往下的節點必須大於它

如果某個節點符合範圍限制，就繼續找他的左右子樹，直到 NULL

```python=
# 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 isValidBST(self, root: Optional[TreeNode]) -> bool:
        lowerBound, upperBound = float("-inf"), float("inf")

        return self.valid(root, lowerBound, upperBound)
        
    def valid(self, node, lowerBound, upperBound):
        if not node:
            return True
        if lowerBound < node.val < upperBound:
            return (self.valid(node.left, lowerBound, node.val) and 
                    self.valid(node.right, node.val, upperBound))
        else:
            return False
```

## 12. Kth Smallest Element in BST
<font color="#ffbb00">**Medium**</font>

> Given the `root` of a binary search tree, and an integer `k`, return the `kth` smallest value (**1-indexed**) in the tree.
>
> A **binary search tree** satisfies the following constraints:
>
> * The left subtree of every node contains only nodes with keys less than the node's key.
> * The right subtree of every node contains only nodes with keys greater than the node's key.
> * Both the left and right subtrees are also binary search trees.

### Example 1:
<img src="https://imagedelivery.net/CLfkmk9Wzy8_9HRyug4EVA/02eca3db-f72f-4277-7134-faec4f02e500/public">

```java
Input: root = [2,1,3], k = 1

Output: 1
```

### Example 2:
<img src="https://imagedelivery.net/CLfkmk9Wzy8_9HRyug4EVA/dca6c42d-2327-4036-f7f2-3e99d8203100/public">

```java
Input: root = [4,3,5,2,null], k = 4

Output: 5
```

### Constraints

* `1 <= k <= The number of nodes in the tree <= 1000`
* `0 <= Node.val <= 1000`


### Recommended complexity

* Time complexity: $O(n)$
* Space complexity: $O(n)$

### Solution

Binary search tree 的中序走訪結果其實就是一個由小排到大的序列。

```python=
# 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 kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.sortedList = []
        self.inOrderTraversal(root)
        
        return self.sortedList[k-1]

    def inOrderTraversal(self, node):
        if node:
            self.inOrderTraversal(node.left)
            self.sortedList.append(node.val)
            self.inOrderTraversal(node.right)
```

:::info
Morris traversal 可以做到 $O(1)$ 的空間複雜度
:::

## 13. Construct Binary Tree From Preorder And Inorder Traversal
<font color="#ffbb00">**Medium**</font>

> You are given two integer arrays `preorder` and `inorder`.
>
> * `preorder` is the preorder traversal of a binary tree
> * `inorder` is the inorder traversal of the same tree
> * Both arrays are of the same size and consist of unique values.
> 
> Rebuild the binary tree from the preorder and inorder traversals and return its root.

### Example 1:
<img src="https://imagedelivery.net/CLfkmk9Wzy8_9HRyug4EVA/938c14d3-6669-47ab-924b-a1a08640f200/public">

```java
Input: preorder = [1,2,3,4], inorder = [2,1,3,4]

Output: [1,2,3,null,null,null,4]
```

### Example 2:
```java
Input: preorder = [1], inorder = [1]

Output: [1]
```

### Constraints

* `1 <= inorder.length <= 1000`
* `inorder.length == preorder.length`
* `-1000 <= preorder[i], inorder[i] <= 1000`

### Recommended complexity

* Time complexity: $O(n)$
* Space complexity: $O(n)$

### Solution

仔細觀察中序與前序的走訪可以發現兩件事：

* Inorder 的結果：以 root 為中間點，左右兩側分別是左子樹與右子樹的節點結合
* Preorder 的結果：第一個位置就是 root

根據上述兩個走訪方法的性質，可以重建ㄧ顆 binary tree 如下(step-by-step)

* 從 preorder 的首項找到根節點
* 從 inorder 確定根節點後，左右分為兩顆子樹
    * 左子樹接上根節點的左節點，繼續遞迴
    * 右子樹接上根節點的右節點，繼續遞迴
* 每次遞迴結束回傳該子樹的根節點

要注意的是遞迴時傳入的 preorder 和 inorder 的 index 編號。

```python=
# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        
        if not preorder:
            return None
        
        root = TreeNode(preorder[0])
        treeLen = len(inorder)

        for i in range(treeLen):
            if inorder[i] == root.val:
                root.left = self.buildTree(preorder[1:i+1], inorder[0:i])
                root.right = self.buildTree(preorder[i+1:], inorder[i+1:])
        return root
```

## 14. Binary Tree Maximum Path Sum
<font color="#ee2f56">**Hard**</font>

> Given the `root` of a non-empty binary tree, return the maximum **path sum** of any non-empty path.
>
> A **path** in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge connecting them. A node can not appear in the sequence more than once. The path does not necessarily need to include the root.
>
> The **path sum** of a path is the sum of the node's values in the path.

### Example 1:
<img src="https://imagedelivery.net/CLfkmk9Wzy8_9HRyug4EVA/9896b041-9021-44c2-ab3e-5cff76adf100/public">
```java
Input: root = [1,2,3]

Output: 6
```

Explanation: The path is 2 -> 1 -> 3 with a sum of 2 + 1 + 3 = 6.


### Example 2:
<img src="https://imagedelivery.net/CLfkmk9Wzy8_9HRyug4EVA/19ce1187-387e-4323-f2c9-1a317ab36200/public">
```java
Input: root = [-15,10,20,null,null,15,5,-5]

Output: 40
```

Explanation: The path is 15 -> 20 -> 5 with a sum of 15 + 20 + 5 = 40.

### Constraints

* `1 <= The number of nodes in the tree <= 1000`
* `-1000 <= Node.val <= 1000`

### Recommended complexity

* Time complexity: $O(n)$
* Space complexity: $O(n)$

### Solution

當路徑經過某個節點時，需要考慮哪些資訊才能計算通過該節點的 path sum ?

* 同時包含左右子樹的路徑
* 只包含左/右其中一個子樹的路徑
* 不含左右子樹，只包含該節點以及其父節點的路徑

但事實上第三種路徑(包含父節點)的算法已經在走訪的過程中包含在第二種(單邊路徑)了，所以不用再計算。

```python=
# 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 maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.res = float("-inf")
        self.traversal(root)
        return self.res

    def getOneSideSum(self, node):
        if not node:
            return 0
        leftSum = self.getOneSideSum(node.left)
        rightSum = self.getOneSideSum(node.right)
        pathSum = node.val + max(leftSum, rightSum)

        return max(0, pathSum)
    
    def traversal(self, node):
        if node:
            leftSum = self.getOneSideSum(node.left)
            rightSum = self.getOneSideSum(node.right)
            self.res = max(self.res, node.val + leftSum + rightSum)
            self.traversal(node.left)
            self.traversal(node.right)
```

## 15. Serialize And Deserialize Binary Tree
<font color="#ee2f56">**Hard**</font>

> Implement an algorithm to serialize and deserialize a binary tree.
>
> Serialization is the process of converting an in-memory structure into a sequence of bits so that it can be stored or sent across a network to be reconstructed later in another computer environment.
>
> You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure. There is no additional restriction on how your serialization/deserialization algorithm should work.
>
> **Note**: The input/output format in the examples is the same as how NeetCode serializes a binary tree. You do not necessarily need to follow this format.

### Example 1:
<img src="https://imagedelivery.net/CLfkmk9Wzy8_9HRyug4EVA/a9dfb17f-70e9-42a3-ba97-33cfd82f6100/public">

```java
Input: root = [1,2,3,null,null,4,5]

Output: [1,2,3,null,null,4,5]
```

### Example 2:
```java
Input: root = []

Output: []
```

### Constraints

* `0 <= The number of nodes in the tree <= 1000`
* `-1000 <= Node.val <= 1000`

### Recommended complexity

* Time complexity: $O(n)$
* Space complexity: $O(n)$

### Solution

這題的序列化(serialize)與反序列化(deserialize)其實就是把樹的內容轉成某種形式的編碼，再想辦法把這個編碼還原成相同結構的樹即可，最簡單的方式是用 traversal 的方式編碼，走訪路徑的的結果就是輸出的編碼。這邊使用前序走訪。

從 Example. 1 為例，前序走訪的結果為 `output = [1, 2, NULL, NULL, 3, 4, NULL, NULL, 5]`。從前面的題目以及前序走訪的性質我們可以知道以下幾件事：

* 輸出結果的第一個 `output[0]` 必定是 root
* root 的下一個 `output[1]` 必定是 left subtree
    * 將 left subtree `output[1]` 視為根節點
    * 下一個 `OUTPUT[2]` 又是 left subtree
    * 直到遇到 `NULL` 表示這個子樹結束
    * 下一個是同 level 的 right subtree

依照上述方式就可以只使用一個走訪方式就把編碼還原成樹。但因為是以遞迴方式進行，編碼不能用迴圈的方式進行，所以要在遞迴函數外部額外設計一個全域變數作為指標，指向目前正在處理的字元。並在遞迴函式內部仿照 while 一樣，不斷增加指標的值來代替遞迴。

```python=
# 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 Codec:
    
    # Encodes a tree to a single string.
    def serialize(self, root: Optional[TreeNode]) -> str:
        self.res = []
        self.preOrder(root)

        return ','.join(self.res)

    # Decodes your encoded data to tree.
    def deserialize(self, data: str) -> Optional[TreeNode]:
        self.vals = data.split(',')
        self.idx = 0
        root = self.inversePreOrder()
        
        return root
    
    def preOrder(self, node):
        if not node:
            self.res.append("N")
            return
        self.res.append(str(node.val))
        self.preOrder(node.left)
        self.preOrder(node.right)
    
    def inversePreOrder(self):
        if self.vals[self.idx] == "N": # this subtree done
            self.idx += 1
            return None
        root = TreeNode(int(self.vals[self.idx]))
        self.idx += 1
        
        root.left = self.inversePreOrder()
        root.right = self.inversePreOrder()
        return root
```
