# 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:
```java
Input: root = [1,2,3,4,5,6,7]
Output: [1,3,2,7,6,5,4]
```
### Example 2:
```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:
```java
Input: root = [1,2,3,null,null,4]
Output: true
```
### Example 2:
```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:
```java
Input: p = [1,2,3], q = [1,2,3]
Output: true
```
### Example 2:
```java
Input: p = [4,7], q = [4,null,7]
Output: false
```
### Example 3:
```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:
```java
Input: root = [1,2,3,4,5], subRoot = [2,4,5]
Output: true
```
### Example 2:
```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:
```java
Input: root = [5,3,8,1,4,7,9,null,2], p = 3, q = 8
Output: 5
```
### Example 2:
```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:
```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:
```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
```
Sign in with Wallet
Connect another wallet