大部分會碰到的是 Binary Tree 和 Binary Search Tree。

常見錯誤：null pointer

指針類型的 linked list, tree, graph 們，都會有的共同錯誤。
前面 linked list 有提過了，
一樣就是在取值（left, right, value）時多注意是否為 None。

Recursive、Iterative 都要會

基本上樹的題型就是先好好掌握下面幾個基礎的 iterative / recursive ：
144. Binary Tree Preorder Traversal
94. Binary Tree Inorder Traversal
145. Binary Tree Postorder Traversal
102. Binary Tree Level Order Traversal

然後多寫其他題型，練習遞迴的思維：
101. Symmetric Tree
257. Binary Tree Paths
...
通常先想清楚遞迴，有餘力就思考這題用 dfs 比較好？還是 bfs 比較好？理由和 complexity 分析。
以及嘗試用 stack 和 queue 實作 iterative，以免面試的時候不讓寫遞迴。

遞迴時如何帶值到外面 function

以 tree 題型來說，通常 Easy 就是很直觀、不太需要另一個 helper function。
Medium 則通常需要 helper function，因為遞迴之間傳遞的值並不是最後需要的答案。
但不建議這樣判斷啦.. 先把難度遮掉，好好思考吧ＸＤ

要帶值出去外層或是紀錄答案，大概有 3 種方法：

1. 放在 instance attribute

def __init__(self):
    self.answer = 0

在遞迴的 function 內部直接取來用
2. nonlocal
Python3 才有
如果我在 solution 裡面寫 inner function，會考慮用 nonlocal keyword 取用外層變數

def solution():
    res = 0
    def recursive():
        nonlocal res
        res += 1
        return blabalbla
    recursive()
    return res

3. 如果是 list，直接傳 ref，甚至不傳

def solution():
    res = []
    def recursive(): 
        res.append("meow!!!")
        return blabalbla
    recursive() # 這邊也可以傳 res 進去，當然上面 function definition 要改
    return res 

總結

樹題目重點就是遞迴思考，
是否能把左右子樹當作ㄧ棵全新的樹丟進現在的 function？
還是要另外構造 helper function？
算是千變萬化，一定要多寫。

有空的話看看之後出一個遞迴心得吧。