給你二叉樹的根節點 root ，回傳它節點值的 前序 遍歷，

示例 1：

輸入：root = [1,null,2,3]
輸出：[1,2,3]
示例 2：

輸入：root = []
輸出：[]
示例 3：

輸入：root = [1]
輸出：[1]
示例 4：

輸入：root = [1,2]
輸出：[1,2]
示例 5：

輸入：root = [1,null,2]
輸出：[1,2]
 

提示：

樹中節點數目在范圍 [0, 100] 內
-100 <= Node.val <= 100
 

進階：遞回演算法很簡單，你可以通過迭代演算法完成嗎？

給定一個二叉樹的根節點 root ，回傳它的 中序 遍歷，

示例 1：

輸入：root = [1,null,2,3]
輸出：[1,3,2]
示例 2：

輸入：root = []
輸出：[]
示例 3：

輸入：root = [1]
輸出：[1]
示例 4：

輸入：root = [1,2]
輸出：[2,1]
示例 5：

輸入：root = [1,null,2]
輸出：[1,2]
 

提示：

樹中節點數目在范圍 [0, 100] 內
-100 <= Node.val <= 100

給定一個二叉樹，回傳它的 后序 遍歷，

示例:

輸入: [1,null,2,3]  
   1
    \
     2
    /
   3 

輸出: [3,2,1]
進階: 遞回演算法很簡單，你可以通過迭代演算法完成嗎？

給你一個二叉樹，請你回傳其按 層序遍歷 得到的節點值， （即逐層地，從左到右訪問所有節點），

示例：
二叉樹：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
回傳其層序遍歷結果：

[
  [3],
  [9,20],
  [15,7]
]

給定一個二叉樹，找出其最大深度，

二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數，

說明: 葉子節點是指沒有子節點的節點，

示例：
給定二叉樹 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7
回傳它的最大深度 3 ，

給定一個二叉樹，檢查它是否是鏡像對稱的，

例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的，

    1
   / \
  2   2
 / \ / \
3  4 4  3
 

但是下面這個 [1,2,2,null,3,null,3] 則不是鏡像對稱的:

    1
   / \
  2   2
   \   \
   3    3
 

進階：

你可以運用遞回和迭代兩種方法解決這個問題嗎？

給你二叉樹的根節點 root 和一個表示目標和的整數 targetSum ，判斷該樹中是否存在 根節點到葉子節點 的路徑，這條路徑上所有節點值相加等于目標和 targetSum ，如果存在，回傳 true ；否則，回傳 false ，

葉子節點 是指沒有子節點的節點，

示例 1：

輸入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
輸出：true
解釋：等于目標和的根節點到葉節點路徑如上圖所示，
示例 2：

輸入：root = [1,2,3], targetSum = 5
輸出：false
解釋：樹中存在兩條根節點到葉子節點的路徑：
(1 --> 2): 和為 3
(1 --> 3): 和為 4
不存在 sum = 5 的根節點到葉子節點的路徑，
示例 3：

輸入：root = [], targetSum = 0
輸出：false
解釋：由于樹是空的，所以不存在根節點到葉子節點的路徑，

根據一棵樹的中序遍歷與后序遍歷構造二叉樹，

注意:
你可以假設樹中沒有重復的元素，

例如，給出

中序遍歷 inorder = [9,3,15,20,7]
后序遍歷 postorder = [9,15,7,20,3]
回傳如下的二叉樹：

    3
   / \
  9  20
    /  \
   15   7

給定一棵樹的前序遍歷 preorder 與中序遍歷  inorder，請構造二叉樹并回傳其根節點，

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]
 

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均無重復元素
inorder 均出現在 preorder
preorder 保證為二叉樹的前序遍歷序列
inorder 保證為二叉樹的中序遍歷序列

給定一個 完美二叉樹 ，其所有葉子節點都在同一層，每個父節點都有兩個子節點，二叉樹定義如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
填充它的每個 next 指標，讓這個指標指向其下一個右側節點，如果找不到下一個右側節點，則將 next 指標設定為 NULL，

初始狀態下，所有 next 指標都被設定為 NULL，

進階：

你只能使用常量級額外空間，
使用遞回解題也符合要求，本題中遞回程式占用的堆疊空間不算欄位外的空間復雜度，
 

示例：

輸入：root = [1,2,3,4,5,6,7]
輸出：[1,#,2,3,#,4,5,6,7,#]
解釋：給定二叉樹如圖 A 所示，你的函式應該填充它的每個 next 指標，以指向其下一個右側節點，如圖 B 所示，序列化的輸出按層序遍歷排列，同一層節點由 next 指標連接，'#' 標志著每一層的結束，
 

提示：

樹中節點的數量少于 4096
-1000 <= node.val <= 1000

給定一個二叉樹

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
填充它的每個 next 指標，讓這個指標指向其下一個右側節點，如果找不到下一個右側節點，則將 next 指標設定為 NULL，

初始狀態下，所有 next 指標都被設定為 NULL，

進階：

你只能使用常量級額外空間，
使用遞回解題也符合要求，本題中遞回程式占用的堆疊空間不算欄位外的空間復雜度，
 

示例：

輸入：root = [1,2,3,4,5,null,7]
輸出：[1,#,2,3,#,4,5,7,#]
解釋：給定二叉樹如圖 A 所示，你的函式應該填充它的每個 next 指標，以指向其下一個右側節點，如圖 B 所示，序列化輸出按層序遍歷順序（由 next 指標連接），'#' 表示每層的末尾，
 

提示：

樹中的節點數小于 6000
-100 <= node.val <= 100

給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先，

百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個節點 p、q，最近公共祖先表示為一個節點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先），”

示例 1：

輸入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出：3
解釋：節點 5 和節點 1 的最近公共祖先是節點 3 ，
示例 2：

輸入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出：5
解釋：節點 5 和節點 4 的最近公共祖先是節點 5 ，因為根據定義最近公共祖先節點可以為節點本身，
示例 3：

輸入：root = [1,2], p = 1, q = 2
輸出：1
 

提示：

樹中節點數目在范圍 [2, 105] 內，
-109 <= Node.val <= 109
所有 Node.val 互不相同 ，
p != q
p 和 q 均存在于給定的二叉樹中，

序列化是將一個資料結構或者物件轉換為連續的位元位的操作，進而可以將轉換后的資料存盤在一個檔案或者記憶體中，同時也可以通過網路傳輸到另一個計算機環境，采取相反方式重構得到原資料，

請設計一個演算法來實作二叉樹的序列化與反序列化，這里不限定你的序列 / 反序列化演算法執行邏輯，你只需要保證一個二叉樹可以被序列化為一個字串并且將這個字串反序列化為原始的樹結構，

提示: 輸入輸出格式與 LeetCode 目前使用的方式一致，詳情請參閱 LeetCode 序列化二叉樹的格式，你并非必須采取這種方式，你也可以采用其他的方法解決這個問題，

示例 1：

輸入：root = [1,2,3,null,null,4,5]
輸出：[1,2,3,null,null,4,5]
示例 2：

輸入：root = []
輸出：[]
示例 3：

輸入：root = [1]
輸出：[1]
示例 4：

輸入：root = [1,2]
輸出：[1,2]
 

提示：

樹中結點數在范圍 [0, 104] 內
-1000 <= Node.val <= 1000