一、二叉樹的思維模式
- 二叉樹的解題模式大致分為兩類：
- 是否可以通過遍歷一遍得解
- 是否可以定義一個遞迴函數，通過分治法推導出原問題的答案？
- 以此題為例，可以遍歷完整個樹，並比較當下的樹的深度，得以求解。
int depth = 0;
int maxDepth(TreeNode* root){
traverse(root, 1);
return depth;
}
void traverse(TreeNode* root, int currDepth){
if (!root) return;
traverse(root->left, currDepth+1);
depth = max(depth, currDepth);
traverse(root->right, currDepth+1);
}
- 若想辦法定義一個遞迴函數，通過分治法推導出原問題，換言之，就是先處理更小的樹，再藉由小的樹處理大的樹：
int maxDepth(TreeNode* root) {
if (root == NULL) return 0;
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
- 事實上，兩個思維模式便對應著兩種演算法：回溯法(back tracking)與動態規劃(dynamic programming)
二、前序、中序、後序
- 無論使用哪種思維模式(遍歷或找出遞迴函數)，都要思考單獨抽出一個節點，它需要在何時(前、中、後序)做哪些事情，其它的節點交由遞迴函數去執行相同的操作。
- 以下我們以 quick sort 與 merge sort 為例，同樣是分治法，看看在數組上有什麼同樣的思維模式。
quick sort
void sort(vector<int>& nums, int left, int right){
if (left >= right) return; // 終止條件
int mid = partition(nums, left, right); // 做什麼事(pre-order)
sort(nums, left, mid-1); // 左子樹
sort(nums, mid+1, right); // 右子樹
}
int partition(vector<int>& nums, int left, int right){
int pivot = right;
while (left < right){
while (nums[left] < nums[pivot]) left++;
while (nums[right] > nums[pivot]) right--;
if (left < right) swap(nums[left], nums[right]);
}
if (left == right && nums[left] > nums[pivot] || nums[right] < nums[pivot]){
swap(nums[left], pivot);
return left;
}
return pivot;
}
merge sort
void sort(vector<int>& nums, int left, int right){
if (right <= left) return; // 終止條件
int mid = left + (right-left)/2;
sort(nums, left, mid); // 左子樹
sort(nums, mid+1, right); // 右子樹
merge(nums, left, mid, right); // 做什麼事(post-order)
}
void merge(vector<int>& nums, int left, int mid, int right){
vector<int> vec;
int i = left, j = mid+1;
while (i <= mid && j <= right){
int x = nums[i] < nums[j] ? nums[i++] : nums[j++];
vec.push_back(x);
}
while (i <= mid) vec.push_back(nums[i++]);
while (j <= right) vec.push_back(nums[j++]);
for (int i = left; i <= right; i++)
nums[i] = vec[i-left];
}
- 換言之，以上就是一個遍歷全部節點的函式，所以本質上數組、鏈表、二叉樹都是在做同樣的事。
void traverse(vector<int> nums, int i){
if (i == nums.size()) return;
// pre-order
traverse(nums, i+1);
// post-order
}
void traverse(ListNode* head){
if (!head) return;
// pre-order
traverse(head->next);
// post-order
}
void traverse(TreeNode* root){
if (!root) return;
// pre-order
traverse(root->left);
// in-order
traverse(root->right);
// post-order
}
三、層序遍歷（level-order)
- Level-order 對應於 BFS(Breadth-First Search)，完下當下的層才會進入到下一層。
void traverse(TreeNode* root){
queue<TreeNode*> q;
q.push(root);
while (!q.empty()){
int sz = q.size();
while (sz--){
TreeNode* curr = q.front();
q.pop();
// operation
if (curr->left) q.push(curr->left);
if (curr->right) q. push(curr->right);
}
}
}