Tree Traversal
常見的 DFS traversal 有 preorder、inorder、postorder，三者差在什麼時候處理目前節點。
- Preorder：先處理目前節點，再走左子樹、右子樹
- Inorder：先走左子樹，再處理目前節點，最後走右子樹
- Postorder：先走左子樹、右子樹，最後才處理目前節點
下面是一個很簡單的模板，recursive 寫起來比較簡單直覺，但也可以用 stack 改成 iterative 寫法。
void traversal(TreeNode* root) {
if(root == nullptr) return;
cout << root->val << " "; // preorder
traversal(root->left);
// cout << root->val << " "; // inorder
traversal(root->right);
// cout << root->val << " "; // postorder
}
144. Binary Tree Preorder Traversal
94. Binary Tree Inorder Traversal
145. Binary Tree Postorder Traversal
Level order traversal 的話則是按照層數從上到下、從左到右走訪，通常會用 queue 來實作，如果題目要求一層一層輸出，每一輪需要先記下目前 queue 的大小，這個大小就是當前這一層的節點數。
void levelOrder(TreeNode* root) {
queue<TreeNode*> q;
if (root) q.push(root);
while(!q.empty()) {
int len=q.size();
for(int i= 0; i<len; i++) {
TreeNode* node=q.front();
q.pop();
cout<<node->val<<" ";
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
cout<<"\n";
}
}
102. Binary Tree Level Order Traversal
199. Binary Tree Right Side View：一樣是 BFS，只是每層只取最右邊的節點。
Recursive Tree, Buttom-up DP
下面是滿滿的 LeetCode Tree 題目，從最簡單的開始：(點小箭頭可以打開提示喔～)226. Invert Binary Tree
走訪每個節點，並交換左右子樹。
進階一點的話，需要從 subtree 拿到結果，再把結果 return 給上一層，這種題目要先想清楚 recursive function 的回傳值代表什麼。
100. Same Tree
比較兩棵樹在相同位置上的節點是否都相同，回傳 true 或 false。
101. Symmetric Tree
可以拆成兩棵樹來看。
104. Maximum Depth of Binary Tree
回傳目前節點的最大深度 (左右子樹深度的最大值+1)
112. Path Sum
每次遞迴都要更新 targetSum (扣掉 root->val)，最後在 leaf 檢查剩下的值是否為 0。
113. Path Sum II
和 Path Sum 類似，但還要記錄目前走過的 path。
236. Lowest Common Ancestor of a Binary Tree
如果左右子樹分別找到 p 和 q，目前節點就是 LCA；如果只有一邊找到，就把那一邊的結果往上回傳。
543. Diameter of Binary Tree
回傳值可以代表「從目前節點往下走的最大深度」，另外用一個變數記錄經過目前節點、連接左右子樹的最大直徑。
124. Binary Tree Maximum Path Sum
概念和 diameter 一樣，特別注意一下負數的處理。
另外一類題目是用 traversal 的順序來還原 tree。
105. Construct Binary Tree from Preorder and Inorder Traversal
preorder 的第一個值是 root，對映到 inorder 中的位置可以切出左子樹和右子樹。
106. Construct Binary Tree from Inorder and Postorder Traversal
postorder 的最後一個值是 root，對映到 inorder 中的位置可以切出左子樹和右子樹。
Binary Search Tree (BST)
對任意節點來說，左子樹的所有值都要小於目前節點，右子樹的所有值都要大於目前節點，以下為經典的 search、insert、delete。
700. Search in a Binary Search Tree
701. Insert into a Binary Search Tree
TreeNode* searchBST(TreeNode* root, int val) {
if(!root) return nullptr;
if(val == root->val) return root;
if(val < root->val) return searchBST(root->left, val);
return searchBST(root->right, val);
}
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(!root) return new TreeNode(val);
if(val < root->val) root->left=insertIntoBST(root->left, val);
else root->right=insertIntoBST(root->right, val);
return root;
}
TreeNode* deleteNode(TreeNode* root, int key) {
if(!root) return root;
// delete
if(key == root->val){
// 0 or 1 child
if(!root->left){
TreeNode* temp=root->right;
delete root;
return temp;
}
if(!root->right){
TreeNode* temp=root->left;
delete root;
return temp;
}
// 2 child
TreeNode* parent=root;
TreeNode* successor=root->right;
while(successor->left){
parent=successor;
successor=successor->left;
}
successor->left=root->left;
if(parent != root){
parent->left=successor->right;
successor->right=root->right;
}
delete root;
return successor;
}
// search
else if(key < root->val){
root->left=deleteNode(root->left, key);
}
else{
root->right=deleteNode(root->right, key);
}
return root;
}
BST 有一個很重要的性質：inorder traversal 的結果會是由小到大排序。
230. Kth Smallest Element in a BST
利用 inorder 會產生遞增序列，走到第 k 個節點就是答案。
98. Validate Binary Search Tree
不能只檢查左右 child，還要確保整棵左子樹都小於 root、整棵右子樹都大於 root，可以遞迴時帶上下界或是跑一次 inorder traversal。
235. Lowest Common Ancestor of a Binary Search Tree
利用 BST 的排序性質，如果 p 和 q 都比目前節點小，就往左走；都比較大，就往右走；否則目前節點就是分岔點，也就是 LCA。
