// 数组遍历框架

// 线性for循环为代表
void traverse(vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {
        // 访问 arr[i]
    }
}

// 非线性递归为代表
void traverse(vector<int>& arr, int idx) {
    if (idx >= arr.size()) {
        return;
    }
    // 访问 arr[i]
    // 递归访问
    traverse(arr, idx + 1);
}

// 链表遍历框架
class listNode {
	public:
    	int val;
    	listNode* next;
};

// 线性for循环
void travsere(listNode* head) {
    for (listNode* cur = head; cur != nullptr; cur = cur->next) {
        // 访问 cur->val
    }
}

// 递归非线性
void travserse(listNode* head) {
    if (head == nullptr) {
        return;
    }
    // 访问 head->val
    // 递归下推
    traverse(head->next);
}

// 二叉树遍历框架 
// 递归非线性 (线性的二叉树用数组存储，不过这种一般是完全二叉树，不具备一般性)
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

void preTraverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // 访问 root->val
    preTraverse(root->left);
    preTraverse(root->right);
}

void inTraverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    preTraverse(root->left);
    // 访问 root->val
    preTraverse(root->right);
}

void postTraverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    preTraverse(root->left);
    preTraverse(root->right);
    // 访问 root->val
}

// 可以观察到，二叉树和链表 用内存指针节点存储的方式是非常像的。
// 抽象出来其实就是 一个节点的子节点数量
// N 叉树 存储和遍历模板
class TreeNode {
    public:
    	int val;
    	vector<TreeNode*> children;
};

void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // 访问节点 root->val
    // 访问子节点
    for (int i = 0; i < root->children.size(); i++) {
        traverse(root->children[i]);
    }
}

/*
N叉树 进一步拓展就是 图（图可以理解为多个N叉树的结合体）
如果有环，用visited做下标记
*/
class GraphNode {
    public:
    	int val;
    	vector<GraphNode*> neighbor;
}

unordered_set<GraphNode*> visited;

void traverse(GraphNode* cur) {
    // 访问当前节点 cur->val
    for (GraphNode* neighbor : cur->neighbor) {
        if (visited.find(neighbor) == visited.end()) {
            visited.insert(neighbor);
            traverse(neighbor);
        }
    }
}

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    // 虚拟头结点
    ListNode* dummy = new ListNode(-1), *p = dummy;
    ListNode* p1 = l1, *p2 = l2;
    
    while (p1 != NULL && p2 != NULL) {
        // 比较 p1 和 p2 两个指针
        // 将值较小的的节点接到 p 指针
        if (p1->val > p2->val) {
            p->next = p2;
            p2 = p2->next;
        } else {
            p->next = p1;
            p1 = p1->next;
        }
        // p 指针不断前进
        p = p->next;
    }
    // 一条链表到底了， 那么剩余的肯定就是另一条链表
    if (p1 != NULL) {
        p->next = p1;
    }
    
    if (p2 != NULL) {
        p->next = p2;
    }
    
    return dummy->next;
}

ListNode* partition(ListNode* head, int x) {
    // 存放小于 x 的链表的虚拟头结点
    ListNode *dummy1 = new ListNode(-1);
    // 存放大于等于 x 的链表的虚拟头结点
    ListNode *dummy2 = new ListNode(-1);
    // p1, p2 指针负责生成结果链表
    ListNode *p1 = dummy1, *p2 = dummy2;
    // p 负责遍历原链表，类似合并两个有序链表的逻辑
    // 这里是将一个链表分解成两个链表
    ListNode *p = head;
    while (p != NULL) {
        if (p->val >= x) {
            p2->next = p;
            p2 = p2->next;
        } else {
            p1->next = p;
            p1 = p1->next;
        }
        // 不能直接让 p 指针前进，
        // p = p.next
        // 断开原链表中的每个节点的 next 指针
        ListNode *temp = p->next;
        p->next = NULL;
        p = temp;
    }
    // 连接两个链表
    p1->next = dummy2->next;

    return dummy1->next;
}

// 不能直接让 p 指针前进，
// p = p.next
// 断开原链表中的每个节点的 next 指针
ListNode temp = p.next;
p.next = null;
p = temp;

如果不断开链表中每个节点的next指针，那么最终结果中会包含一个环。
因为最终是需要拼接两个新链表的。

ListNode* mergeKLists(vector<ListNode*>& lists) {
    if (lists.empty()) return nullptr;
    // 虚拟头结点
    ListNode* dummy = new ListNode(-1);
    ListNode* p = dummy;
    // 优先级队列，最小堆
    priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> pq(
        [] (ListNode* a, ListNode* b) { return a->val > b->val; });
    // 将 k 个链表的头结点加入最小堆
    for (auto head : lists) {
        if (head != nullptr) {
            pq.push(head);
        }
    }

    while (!pq.empty()) {
        // 获取最小节点，接到结果链表中
        ListNode* node = pq.top();
        pq.pop();
        p->next = node;
        if (node->next != nullptr) {
            pq.push(node->next);
        }
        // p 指针不断前进
        p = p->next;
    }
    return dummy->next;
}

// 返回链表的倒数第 k 个节点
ListNode* findFromEnd(ListNode* head, int k) {
    ListNode* p1 = head;
    // p1 先走 k 步
    for (int i = 0; i < k; i++) {
        p1 = p1 -> next;
    }
    ListNode* p2 = head;
    // p1 和 p2 同时走 n - k 步
    while (p1 != nullptr) {
        p2 = p2 -> next;
        p1 = p1 -> next;
    }
    // p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
    return p2;
}

时间复杂度: O (N)

ListNode* middleNode(ListNode* head) {
    // 快慢指针初始化指向 head
    ListNode* slow = head;
    ListNode* fast = head;
    // 快指针走到末尾时停止
    while (fast != nullptr && fast->next != nullptr) {
        // 慢指针走一步，快指针走两步
        slow = slow->next;
        fast = fast->next->next;
    }
    // 慢指针指向中点
    return slow;
}

bool hasCycle(ListNode* head) {
    // 初始化快慢指针，指向头结点
    ListNode* slow = head;
    ListNode* fast = head;
    // 快指针到尾部时停止
    while (fast && fast->next) {
        // 慢指针走一步，快指针走两步
        slow = slow->next;
        fast = fast->next->next;
        // 快慢指针相遇，说明含有环
        if (slow == fast) {
            return true;
        }
    }
    // 不包含环
    return false;
}

// 进阶：如果存在环，怎么找环的起点
ListNode* detectCycle(ListNode* head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while (fast != nullptr && fast->next != nullptr) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) break;

    }
    // 上面的代码类似 hasCycle 函数
    if (fast == nullptr || fast->next == nullptr) {
        // fast 遇到空指针说明没有环
        return nullptr;
    }

    // 重新指向头结点
    slow = head;

    // 快慢指针同步前进，相交点就是环起点
    /*
    慢指针：k 步  快指针：2k 步
    假设相遇点距环起点 m 步， 那么相遇点距起点 k - m 步
    快指针距离再次到达相遇点 2k - k - m 步 = k - m 步
    */
    while (slow != fast) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

int removeDuplicates(vector<int>& nums) {
    if (nums.size() == 0) {
        return 0;
    }
    int slow = 0, fast = 0;
    while (fast < nums.size()) {
        if (nums[fast] != nums[slow]) {
            slow++;
            // 维护 nums[0..slow] 无重复
            nums[slow] = nums[fast];
        }
        fast++;
    }
    // 数组长度为索引 + 1
    return slow + 1;
}

int removeElement(vector<int>& nums, int val) {
    int fast = 0, slow = 0;
    while (fast < nums.size()) {
        if (nums[fast] != val) {
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }
    return slow;
}

void moveZeroes(vector<int>& nums) {
    // 去除 nums 中的所有 0，返回不含 0 的数组长度
    int p = removeElement(nums, 0);
    // 将 nums[p..] 的元素赋值为 0
    for (; p < nums.size(); p++) {
        nums[p] = 0;
    }
}

// 见上文代码实现
int removeElement(vector<int>& nums, int val);

// 只看双指针特性即可
int binarySearch(vector<int>& nums, int target) {
    // 双指针，从左右到中间
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        }
     	else if (nums[mid] < target) {
            left = mid + 1;
        }   
        else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    return -1;
}

vector<int> twoSum(vector<int>& nums, int target) {
    // 一左一右两个指针相向而行
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            // 题目要求的索引是从 1 开始的
            return {left + 1, right + 1};
        } else if (sum < target) {
            left++; // 让 sum 大一点
        } else if (sum > target) {
            right--; // 让 sum 小一点
        }
    }
    return {-1, -1};
}

void reverseString(vector<char>& s) {
    // 一左一右两个指针相向而行
    int left = 0, right = s.size() - 1;
    while (left < right) {
        // 交换 s[left] 和 s[right]
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
}

bool isPalindrome(string s) {
    // 一左一右两个指针相向而行
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s[left] != s[right]) { // 如果不相同，就不是回文串
            return false;
        }
        left++;
        right--;
    }
    return true;
}

// 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
string palindrome(string s, int l, int r) {
    // 防止索引越界
    while (l >= 0 && r < s.length()
            && s[l] == s[r]) {
        // 双指针，向两边展开
        l--; r++;
    }
    // 返回以 s[l] 和 s[r] 为中心的最长回文串
    return s.substr(l + 1, r - l - 1);
}

string longestPalindrome(string s) {
    string res = "";
    for (int i = 0; i < s.length(); i++) {
        // 以 s[i] 为中心的最长回文子串
        string s1 = palindrome(s, i, i);
        // 以 s[i] 和 s[i+1] 为中心的最长回文子串
        string s2 = palindrome(s, i, i + 1);
        // res = longest(res, s1, s2)
        res = res.length() > s1.length() ? res : s1;
        res = res.length() > s2.length() ? res : s2;
    }
    return res;
}

int left = 0, right = 0;

while (right < nums.size()) {
    // 增大窗口
    window.add(nums[right]);
    right++;
    
    while (window needs shrink) {
        // 缩小窗口
        window.remove(nums[left]);
        left++;
    }
}

// 滑动窗口 的等价暴力写法就是 双重for循环
// 时间复杂度上 滑动窗口O(N)  暴力解法O(N^2)
// 窗口的指针都是不回退的，那么最多就是N + N 
// 滑动窗口没办法枚举所有子数组，因为它的移动规则是有限定的

// 以求解子串问题为例
void slidingWindow(string s) {
    // 用合适的数据结构记录窗口中的数据，根据具体场景变通
    // such as 记录窗口中元素出现的次数，用map
    // 记录窗口中元素和，就用int
    unordered_map<char, int> window;
    
    int left = 0, right = 0;
    while (right < s.size()) {
        // c 就是将移入窗口的字符
        char c = s[right];
        window.add(c);
        //增大窗口
        right++;
        // 对窗口中数据进行更新
        ...
            
        // debug的位置
        printf("window: [%d, %d]\n", left, right);
        
        // 判断左侧窗口是否要压缩
        while (left < right && window needs shrink) {
            // d 就是要移出窗口的字符
            char d = s[left];
            window.remove(d);
            // 缩小窗口
            left++;
            // 对窗口内数据进行更新
            ...
        }
    }
}

string minWindow(string s, string t) {
    // need用于记录t，window用于记录窗口内容
	unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    
    int left = 0, right = 0;
    int valid = 0;
    // 记录最小覆盖子串的起始索引和长度
    int start = 0, len = INT_MAX;
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 扩大窗口
        right++;
        // 进行窗口内数据更新
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) {
                valid++;
            }
        }
        
        // 判断左侧窗口是否要压缩
        while (valid == need.size()) {
            // 在这里更新最小覆盖子串
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            // d 是将移出窗口的字符
            char d = s[left];
            // 缩小窗口
            left++;
            // 进行窗口内数据更新
            if (need.count(d)) {
                if (window[d] == need[d]) {
                    valid--;
                }
                window[d]--;
            }
        }
    }
    return len == INT_MAX ? "" : s.substr(start, len);
}

// 判断 s 中是否存在 t 的排列
bool checkInclusion(string t, string s) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    while (right < s.size()) {
        char c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c])
                valid++;
        }

        // 判断左侧窗口是否要收缩
        while (right - left >= t.size()) {
            // 在这里判断是否找到了合法的子串
            if (valid == need.size())
                return true;
            char d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d)) {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    // 未找到符合条件的子串
    return false;
}

由于这道题中 [left, right) 其实维护的是一个定长的窗口，窗口大小为 t.size()。因为定长窗口每次向前滑动时只会移出一个字符，所以可以把内层的 while 改成 if，效果是一样的。

vector<int> findAnagrams(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    vector<int> res; // 记录结果
    while (right < s.size()) {
        char c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) 
                valid++;
        }
        // 判断左侧窗口是否要收缩
        while (right - left >= t.size()) {
            // 当窗口符合条件时，把起始索引加入 res
            if (valid == need.size())
                res.push_back(left);
            char d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d)) {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    return res;
}

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> window;

    int left = 0, right = 0;
    int res = 0; // 记录结果
    while (right < s.size()) {
        char c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        window[c]++;
        // 判断左侧窗口是否要收缩
        while (window[c] > 1) {
            char d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            window[d]--;
        }
        // 在这里更新答案
        res = max(res, right - left);
    }
    return res;
}

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;

    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    return ...;
}

int binarySearch(vector<int>& nums, int target) {
    int left = 0; 
    int right = nums.size() - 1; // 注意

    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
    }
    return -1;
}

    if(nums[mid] == target)
        return mid;

    //...
    while(left < right) {
        // ...
    }
    return nums[left] == target ? left : -1;

int left_bound(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size(); // 注意
    
    while (left < right) { // 注意
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

// 函数返回 nums 数组中最左侧的 target的索引

while (left < right) {
    //...
}
// 如果索引越界，说明数组中无目标元素，返回 -1
if (left < 0 || left >= nums.length) {
    return -1;
}
// 提示：其实上面的 if 中 left < 0 这个判断可以省略，因为对于这个算法，left 不可能小于 0
// 你看这个算法执行的逻辑，left 初始化就是 0，且只可能一直往右走，那么只可能在右侧越界
// 不过我这里就同时判断了，因为在访问数组索引之前保证索引在左右两端都不越界是一个好习惯，没有坏处
// 另一个好处是让二分的模板更统一，降低你的记忆成本，因为等会儿寻找右边界的时候也有类似的出界判断


// 判断一下 nums[left] 是不是 target
return nums[left] == target ? left : -1;

int left_bound(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    // 搜索区间为 [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 收缩右侧边界
            right = mid - 1;
        }
    }
    // 判断 target 是否存在于 nums 中
    // 如果越界，target 肯定不存在，返回 -1
    if (left < 0 || left >= nums.size()) {
        return -1;
    }
    // 判断一下 nums[left] 是不是 target
    return nums[left] == target ? left : -1;
}

int right_bound(vector<int>& nums, int target) {
    int left = 0, right = nums.size();

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1; // 注意
}

if (nums[mid] == target) {
    left = mid + 1;

// 增大 left，锁定右侧边界
if (nums[mid] == target) {
    left = mid + 1;
    // 这样想: mid = left - 1

while (left < right) {
    // ...
}
// 判断 target 是否存在于 nums 中
// left - 1 索引越界的话 target 肯定不存在
if (left - 1 < 0 || left - 1 >= nums.size()) {
    return -1;
}
// 判断一下 nums[left - 1] 是不是 target
return nums[left - 1] == target ? (left - 1) : -1;

int right_bound(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 这里改成收缩左侧边界即可
            left = mid + 1;
        }
    }
    // 最后改成返回 left - 1
    if (left - 1 < 0 || left - 1 >= nums.size()) {
        return -1;
    }
    return nums[left - 1] == target ? (left - 1) : -1;
}

因为我们初始化 right = nums.length - 1
所以决定了我们的「搜索区间」是 [left, right]
所以决定了 while (left <= right)
同时也决定了 left = mid+1 和 right = mid-1

因为我们只需找到一个 target 的索引即可
所以当 nums[mid] == target 时可以立即返回

因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid + 1 和 right = mid

因为我们需找到 target 的最左侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧右侧边界以锁定左侧边界 right = mid

因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid + 1 和 right = mid

因为我们需找到 target 的最右侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧左侧边界以锁定右侧边界

又因为收紧左侧边界时必须 left = mid + 1
所以最后无论返回 left 还是 right，必须减一

void sort(vector<int>& nums, int lo, int hi) {
    // ****** 前序遍历位置 ******
    // 通过交换元素构建分界点 p
    int p = partition(nums, lo, hi);
    // ************************

    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}
// 先构造分界点，然后去左右子数组构造分界点，你看这不就是一个二叉树的前序遍历吗？

// 定义：排序 nums[lo..hi]
void sort(vector<int>& nums, int lo, int hi) {
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    // 排序 nums[lo..mid]
    sort(nums, lo, mid);
    // 排序 nums[mid+1..hi]
    sort(nums, mid + 1, hi);

    // ****** 后序位置 ******
    // 合并 nums[lo..mid] 和 nums[mid+1..hi]
    merge(nums, lo, mid, hi);
    // *********************
}

// 先对左右子数组排序，然后合并（类似合并有序链表的逻辑），你看这是不是二叉树的后序遍历框架？另外，这不就是传说中的分治算法嘛。

// 迭代遍历数组
void traverse(vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {

    }
}

// 递归遍历数组
void traverse(vector<int>& arr, int i) {
    if (i == arr.size()) {
        return;
    }
    // 前序位置
    traverse(arr, i + 1);
    // 后序位置
}

struct ListNode {
    int val;
    ListNode *next;
};

// 迭代遍历单链表
void traverse(ListNode* head) {
    for (ListNode* p = head; p != nullptr; p = p->next) {

    }
}

// 递归遍历单链表
void traverse(ListNode* head) {
    if (head == nullptr) {
        return;
    }
    // 前序位置
    traverse(head->next);
    // 后序位置
}

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode * right;
};

// 递归遍历二叉树
void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // 前序位置
    traverse(root->left);
    // 中序位置
    traverse(root->right);
    // 后序位置
}

// 记录最大深度
int res = 0;
// 记录遍历到的节点的深度
int depth = 0;

// 主函数
int maxDepth(TreeNode* root) {
    traverse(root);
    return res;
}

// 二叉树遍历框架
void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // 前序位置
    depth++;
    if (root->left == nullptr && root->right == nullptr) {
        // 到达叶子节点，更新最大深度
        res = std::max(res, depth);
    }
    traverse(root->left);
    traverse(root->right);
    // 后序位置
    depth--;
}

// 定义：输入根节点，返回这棵二叉树的最大深度
int maxDepth(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    // 利用定义，计算左右子树的最大深度
    int leftMax = maxDepth(root->left);
    int rightMax = maxDepth(root->right);
    // 整棵树的最大深度等于左右子树的最大深度取最大值，
    // 然后再加上根节点自己
    int res = std::max(leftMax, rightMax) + 1;
    
    return res;
}

#include <list>

std::list<int> res;

// 返回前序遍历结果
std::list<int> preorderTraverse(TreeNode* root) {
    traverse(root);
    return res;
}

// 二叉树遍历函数
void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    
    // 前序位置
    res.push_back(root->val);
    traverse(root->left);
    traverse(root->right);
}

// 定义：输入一棵二叉树的根节点，返回这棵树的前序遍历结果
vector<int> preorderTraverse(TreeNode* root) {
    vector<int> res;
    if (root == nullptr) {
        return res;
    }
    // 前序遍历的结果，root->val 在第一个
    res.push_back(root->val);
    // 利用函数定义，后面接着左子树的前序遍历结果
    vector<int> left = preorderTraverse(root->left);
    res.insert(res.end(), left.begin(), left.end());
    // 利用函数定义，最后接着右子树的前序遍历结果
    vector<int> right = preorderTraverse(root->right);
    res.insert(res.end(), right.begin(), right.end());


    return res;
}

// 二叉树遍历函数
void traverse(TreeNode* root, int level) {
    if (root == nullptr) {
        return;
    }
    // 前序位置
    printf("节点 %s 在第 %d 层", root->val, level);
    traverse(root->left, level + 1);
    traverse(root->right, level + 1);
}

// 这样调用
traverse(root, 1);

// Definition for a binary tree node.
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 定义：输入一棵二叉树，返回这棵二叉树的节点总数
int count(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    int leftCount = count(root->left);
    int rightCount = count(root->right);
    // 后序位置
    printf("节点 %p 的左子树有 %d 个节点，右子树有 %d 个节点",
            root, leftCount, rightCount);

    return leftCount + rightCount + 1;
}

class Solution {
public:
    // 记录最大直径的长度
    int maxDiameter = 0;

    int diameterOfBinaryTree(TreeNode* root) {
        // 对每个节点计算直径，求最大直径
        traverse(root);
        return maxDiameter;
    }

private:
    // 遍历二叉树
    void traverse(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        // 对每个节点计算直径
        int leftMax = maxDepth(root->left);
        int rightMax = maxDepth(root->right);
        int myDiameter = leftMax + rightMax;
        // 更新全局最大直径
        maxDiameter = max(maxDiameter, myDiameter);

        traverse(root->left);
        traverse(root->right);
    }

    // 计算二叉树的最大深度
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int leftMax = maxDepth(root->left);
        int rightMax = maxDepth(root->right);
        return 1 + max(leftMax, rightMax);
    }
};

class Solution {
    // 记录最大直径的长度
    int maxDiameter = 0;

public:
    int diameterOfBinaryTree(TreeNode* root) {
        maxDepth(root);
        return maxDiameter;
    }

    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int leftMax = maxDepth(root->left);
        int rightMax = maxDepth(root->right);
        // 后序位置，顺便计算最大直径
        int myDiameter = leftMax + rightMax;
        maxDiameter = max(maxDiameter, myDiameter);

        return 1 + max(leftMax, rightMax);
    }
};

// 定义：输入一棵二叉树，返回这棵二叉树的节点总数
int count(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    // 当前节点关心的是两个子树的节点总数分别是多少
    // 因为用子问题的结果可以推导出原问题的结果
    int leftCount = count(root->left);
    int rightCount = count(root->right);
    // 后序位置，左右子树节点数加上自己就是整棵树的节点数
    return leftCount + rightCount + 1;
}

// 这就是动态规划分解问题的思路，它的着眼点永远是结构相同的整个子问题，类比到二叉树上就是「子树」。

void traverse(TreeNode* root) {
    // 如果节点为空（说明已经越过叶节点），就返回
    if (root == nullptr) return;
    // 从节点 root 出发，沿着 left 边走
    printf("从节点 %s 进入节点 %s", root, root->left);
    traverse(root->left);
    // 从节点 root 的左边回来
    printf("从节点 %s 回到节点 %s", root->left, root);

    // 从节点 root 出发，沿着 right 边走
    printf("从节点 %s 进入节点 %s", root, root->right);
    traverse(root->right);
    // 从节点 root 的右边回来
    printf("从节点 %s 回到节点 %s", root->right, root);
}

// 这就是回溯算法遍历的思路，它的着眼点永远是在节点之间移动的过程，类比到二叉树上就是「树枝」。

void traverse(TreeNode* root) {
    if (root == nullptr) return;
    // 遍历过的每个节点的值加一
    root->val++;
    traverse(root->left);
    traverse(root->right);
}
// 这就是 DFS 算法遍历的思路，它的着眼点永远是在单一的节点上，类比到二叉树上就是处理每个「节点」。

// DFS 算法把「做选择」「撤销选择」的逻辑放在 for 循环外面
void dfs(Node* root) {
    if (!root) return;
    // 做选择
    printf("我已经进入节点 %s 啦\n", root->val.c_str());
    for (Node* child : root->children) {
        dfs(child);
    }
    // 撤销选择
    printf("我将要离开节点 %s 啦\n", root->val.c_str());
}

// 回溯算法把「做选择」「撤销选择」的逻辑放在 for 循环里面
void backtrack(Node* root) {
    if (!root) return;
    for (Node* child : root->children) {
        // 做选择
        printf("我站在节点 %s 到节点 %s 的树枝上\n", root->val.c_str(), child->val.c_str());
        backtrack(child);
        // 撤销选择
        printf("我将要离开节点 %s 到节点 %s 的树枝上\n", child->val.c_str(), root->val.c_str());
    }
}

// 层序遍历属于迭代思维
// 输入一棵二叉树的根节点，层序遍历这棵二叉树
void levelTraverse(TreeNode* root) {
    if (root == nullptr) return;
    queue<TreeNode*> q;
    q.push(root);

    // 从上到下遍历二叉树的每一层
    while (!q.empty()) {
        int sz = q.size();
        // 从左到右遍历每一层的每个节点
        for (int i = 0; i < sz; i++) {
            TreeNode* cur = q.front();
            q.pop();
            // 将下一层节点放入队列
            if (cur->left != nullptr) {
                q.push(cur->left);
            }
            if (cur->right != nullptr) {
                q.push(cur->right);
            }
        }
    }
}

class Solution {
public:
    vector<vector<int>> res;

    vector<vector<int>> levelTraverse(TreeNode* root) {
        if (root == nullptr) {
            return res;
        }
        // root 视为第 0 层
        traverse(root, 0);
        return res;
    }

    void traverse(TreeNode* root, int depth) {
        if (root == nullptr) {
            return;
        }
        // 前序位置，看看是否已经存储 depth 层的节点了
        if (res.size() <= depth) {
            // 第一次进入 depth 层
            res.push_back(vector<int> {});
        }
        // 前序位置，在 depth 层添加 root 节点的值
        res[depth].push_back(root->val);
        traverse(root->left, depth + 1);
        traverse(root->right, depth + 1);
    }
};

class Solution {
private:
    vector<vector<int>> res;
    
public:
    vector<vector<int>> levelTraverse(TreeNode* root) {
        if (root == NULL) {
            return res;
        }
        vector<TreeNode*> nodes;
        nodes.push_back(root);
        traverse(nodes);
        return res;
    }

    void traverse(vector<TreeNode*>& curLevelNodes) {
        // base case
        if (curLevelNodes.empty()) {
            return;
        }

        // 前序位置，计算当前层的值和下一层的节点列表
        vector<int> nodeValues;
        vector<TreeNode*> nextLevelNodes;
        for (TreeNode* node : curLevelNodes) {
            nodeValues.push_back(node->val);
            if (node->left != NULL) {
                nextLevelNodes.push_back(node->left);
            }
            if (node->right != NULL) {
                nextLevelNodes.push_back(node->right);
            }
        }

        // 前序位置添加结果，可以得到自顶向下的层序遍历
        res.push_back(nodeValues);

        traverse(nextLevelNodes);

        // 后序位置添加结果，可以得到自底向上的层序遍历结果
        // res.push_back(nodeValues);
    }
};

int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

int fib(int N) {
    // 备忘录全初始化为 0
    int memo[N + 1];
    memset(memo, 0, sizeof(memo));
    // 进行带备忘录的递归
    return dp(memo, N);
}

// 带着备忘录进行递归
int dp(int memo[], int n) {
    // base case
    if (n == 0 || n == 1) return n;
    // 已经计算过，不用再计算了
    if (memo[n] != 0) return memo[n];
    memo[n] = dp(memo, n - 1) + dp(memo, n - 2);
    return memo[n];
}

int fib(int N) {
    if (N == 0) return 0;
    int* dp = new int[N + 1];
    // base case
    dp[0] = 0; dp[1] = 1;
    // 状态转移
    for (int i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[N];
}

int dp(vector<int>& coins, int amount);

int coinChange(vector<int>& coins, int amount) {
    // 题目要求的最终结果是 dp(amount)
    return dp(coins, amount);
}

// 定义：要凑出金额 n，至少要 dp(coins, n) 个硬币
int dp(vector<int>& coins, int amount) {
    // base case
    if (amount == 0) return 0;
    if (amount < 0) return -1;

    int res = INT_MAX;
    for (int coin : coins) {
        // 计算子问题的结果
        int subProblem = dp(coins, amount - coin);
        // 子问题无解则跳过
        if (subProblem == -1) continue;
        // 在子问题中选择最优解，然后加一
        res = min(res, subProblem + 1);
    }

    return res == INT_MAX ? -1 : res;
}

class Solution {
    private:
        vector<int> memo;
        
        /**
         * memo 数组记录了 amount 对应的最优解，-1 代表还未被计算。
         * 因此，在计算 amount 对应的最优解时需要先查找 memo。
         */
        int dp(vector<int>& coins, int amount){
            if(amount == 0) return 0; // 如果 amount = 0，那么硬币数量为 0
            if(amount < 0) return -1; // 如果 amount < 0，那么无解
            if(memo[amount] != -1) return memo[amount]; // 查备忘录，如果有最优解则直接返回
            
            int res = INT_MAX;
            /**
             * 在硬币数组 coins 中依次选取每个硬币。
             * 对于当前选择的硬币，计算是包含该硬币所需的子问题的最优解 subProblem。
             * 如果子问题无解，则直接跳过该硬币。
             * 在所有子问题中，选取最优解，并加上该硬币的数量。
             * 最终的结果 res 即为 amount 对应的最优解，该结果存入 memo 中。
             */
            for(int coin : coins){
                int subProblem = dp(coins, amount - coin);
                if(subProblem == -1) continue;
                res = min(res, subProblem + 1);
            }
            
            memo[amount] = res == INT_MAX ? -1 : res;
            return memo[amount];
        }
        
    public:
        int coinChange(vector<int>& coins, int amount) {
            /**
             * 初始化备忘录 memo，memo 数组的长度为 amount+1。
             * memo 数组记录了 amount 对应的最优解，-1 代表还未被计算。
             * 因此，在计算 amount 对应的最优解时需要先查找 memo，再根据结果进行计算。
             */
            memo = vector<int>(amount + 1, -666);
            return dp(coins, amount);
        }
};

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    // 数组大小为 amount + 1，初始值也为 amount + 1
    dp[0] = 0;

    // 外层 for 循环在遍历所有状态的所有取值
    for (int i = 0; i < dp.size(); i++) {
        // 内层 for 循环在求所有选择的最小值
        for (int coin : coins) {
            // 子问题无解，跳过
            if (i - coin < 0) {
                continue;
            }
            dp[i] = min(dp[i], 1 + dp[i - coin]);
        }
    }
    return (dp[amount] == amount + 1) ? -1 : dp[amount];
}

为啥 dp 数组中的值都初始化为 amount + 1 呢，因为凑成 amount 金额的硬币数最多只可能等于 amount（全用 1 元面值的硬币），所以初始化为 amount + 1 就相当于初始化为正无穷，便于后续取最小值。为啥不直接初始化为 int 型的最大值 Integer.MAX_VALUE 呢？因为后面有 dp[i - coin] + 1，这就会导致整型溢出。