class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            unordered_map<int, int> indices;
            for(int i=0; i<nums.size(); i++) indices[nums[i]] = i;

            for(int i=0; i<nums.size(); i++){
                int left = target - nums[i];
                if (indices.count(left) && indices[left]!=i) return {i, indices[left]};
            }
            return {};
        }
    };

// 使用 std::unordered_map
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map <int,int> map;
        for(int i = 0; i < nums.size(); i++) {
            auto iter = map.find(target - nums[i]);
            if(iter != map.end()) return {iter->second, i
            map.insert({nums[i], i});
        }
        return {};
    }
};

    class Solution {
    public:
        int searchInsert(vector<int>& nums, int target) {
            int left = 0;
            int right = nums.size()-1;

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

    class Solution {
    public:
        int removeElement(vector<int>& nums, int val) {
            int slowPointer = 0;
            for(int fastPointer = 0;fastPointer<nums.size();fastPointer++){
                if(nums[fastPointer]!=val){
                    nums[slowPointer++] = nums[fastPointer];
                }
            }
            return slowPointer;
        }
    };

//法二
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int leftIndex = 0;
        int rightIndex = nums.size() -1 ;
        
        while(leftIndex <= rightIndex){
            while(leftIndex <= rightIndex && nums[leftIndex] != val){
                leftIndex++;
            }
            while(leftIndex <= rightIndex && nums[rightIndex] == val){
                rightIndex--;
            }
            if(leftIndex < rightIndex){
                nums[leftIndex] = nums[rightIndex];
                leftIndex++;
                rightIndex--;
                //nums[leftIndex++] = nums[rightIndex--];
            }
        }
        return leftIndex;
    }
};

    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int>> result;
            sort(nums.begin(), nums.end());

            for(int i=0; i<nums.size(); i++){
                int left = i+1;
                int right = nums.size()-1;
                if(nums[i]>0) return result;
                if(i>0 && nums[i]==nums[i-1]) continue;
                while(right>left){
                    if(nums[i]+nums[left]+nums[right] > 0) right--;
                    else if(nums[i]+nums[left]+nums[right] < 0) left++;
                    else{
                        result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                        while(right > left && nums[left]==nums[left+1])left++;
                        while(right > left && nums[right]==nums[right-1])right--;
                        left++;
                        right--;
                    }
                }
            }
            return result;
        }
    };

    class Solution {
    public:
        int minSubArrayLen(int target, vector<int>& nums) {
            int result = INT32_MAX;
            int i = 0;
            int sum = 0;
            for(int j = 0; j < nums.size(); j++){
                sum += nums[j];
                while(sum >= target){
                    result = result < j-i+1 ? result:j-i+1;
                    sum -= nums[i++];
                }
            }
            return result == INT32_MAX ? 0 : result;
        }
    };

    class Solution {
    public:
        vector<vector<int>> generateMatrix(int n) {
            vector<vector<int>> res(n, vector<int>(n, 0));

            int startY = 0;
            int startX = 0;
            int offset = 1;
            int round = n/2;
            int count = 1;
            int mid = n/2;

            while(round--){

                int j = startY;
                int i = startX;

                for(j = startY; j < startY +  n - offset; j++) res[startX][j] = count++;
                for(i = startX; i < startX +  n - offset; i++) res[i][startY +  n - offset] = count++;
                for(; j > startY; j--) res[startY +  n - offset][j] = count++;
                for(; i> startY; i--) res[i][startX] = count++;

                startY++;
                startX++;
                offset += 2;
            }
            if (n % 2) res[mid][mid] = count;
            return res;
        }
    };

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 
    class Solution {
    public:
        ListNode* removeElements(ListNode* head, int val) {

            while(head != NULL && head->val == val){
                ListNode* tmp = head;
                head = head->next;
                delete tmp;
            }

            ListNode* cur = head;

            while(cur != NULL && cur->next != NULL){
                if(cur->next->val == val){
                    ListNode* tmp = cur->next;
                    cur->next = cur->next->next;
                    delete tmp;
                }else{
                    cur = cur->next;
                }
            }
            return head;
        }
    };

    class Solution {
    public:
        ListNode* removeElements(ListNode* head, int val) {

            ListNode* dummyNode = new ListNode(0);
            dummyNode->next = head;
            ListNode* cur = dummyNode;

            while(cur->next != NULL){
                if(cur->next->val == val){
                    ListNode* tmp = cur->next;
                    cur->next = cur->next->next;
                    delete tmp;
                }else{
                    cur = cur->next;
                }
            }
            return dummyNode->next;
        }
    };

class MyLinkedList {
public:
    struct LinkedNode{
    int val;
    LinkedNode* next;
    LinkedNode(int val):val(val), next(nullptr){}
    };
    
    MyLinkedList() {
        _dummyNode = new LinkedNode(0);
        _size = 0;
    }
    
    int get(int index) {
        if(index+1 > _size || index < 0) return-1;
        LinkedNode* cur = _dummyNode->next;
        while(index--) cur = cur->next;
        return cur->val;
    }
    
    void addAtHead(int val) {
        LinkedNode* newhead = new LinkedNode(val);
        newhead->next = _dummyNode->next;
        _dummyNode->next = newhead;
        _size++;
    }
    
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyNode;
        while(cur->next != nullptr) cur = cur->next;
        cur->next = newNode;
        _size++;
    }
    void addAtIndex(int index, int val) {
        if(index > _size) return;
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyNode;
        while(index--) cur = cur->next;
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }
    
    void deleteAtIndex(int index) {
        if(index >= _size || index < 0)return;
        LinkedNode* cur = _dummyNode;
        while(index--) cur = cur->next;
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        _size--; 
    }
private:
    int _size;
    LinkedNode* _dummyNode;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
    class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
            ListNode* pre = NULL;
            ListNode* cur = head;
            ListNode* tmp;

            while(cur){
                tmp = cur->next;
                cur->next = pre;
                pre = cur;
                cur = tmp;
            }
            return pre;
        }
    };

    class Solution {
    public:
        ListNode* reverse(ListNode* pre, ListNode* cur){
            if(!cur)return pre;

            ListNode* tmp = cur->next;
            cur->next = pre;
            return reverse(cur, tmp);
        }


        ListNode* reverseList(ListNode* head) {
            return reverse(NULL, head);
        }
    };

    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
    class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
            ListNode* fast = head;
            ListNode* slow = head;

            while(fast != NULL && fast->next != NULL){
                fast = fast->next->next;
                slow = slow->next;
                if(fast == slow){
                    ListNode* index1 = fast;
                    ListNode* index2 = head;
                    while(index1 != index2){
                        index1 = index1->next;
                        index2 = index2->next;
                    }
                    return index2;
                }

            }
            return NULL;
        }
    };

    class Solution {
    public:
        bool isAnagram(string s, string t) {
            int record[26]={0};
            for(int i = 0; i < s.size(); i++) record[s[i] - 'a']++;
            for(int i = 0; i < t.size(); i++) record[t[i] - 'a']--;
            for(int i = 0; i < 26; i++) if(record[i]) return false;
            return true;
        }
    };

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set;
        unordered_set<int> num_set(nums1.begin(),nums1.end());
        for(int num : nums2){
            if(num_set.find(num) != num_set.end()){
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(),result_set.end());
    }
};

class Solution {
public:
    int toSum(int n){
        int sum = 0;
        while(n){
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> set;
        while(1){
            int num = toSum(n);
            if(num == 1) return true;
            if(set.find(num) != set.end()) return false;
            else set.insert(num);
            n = num;
        }
    }
};

// 使用 std::unordered_map
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map <int,int> map;
        for(int i = 0; i < nums.size(); i++) {
            auto iter = map.find(target - nums[i]);
            if(iter != map.end()) return {iter->second, i};
         // map::insert({key, element})
            map.insert({nums[i], i});
        }
        return {};
    }
};

//暴力解 
//時間複雜度O(n^2)    
//空間複雜度O(1)
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        for(int i = 0; i < magazine.length(); i++){
            for(int j = 0; j < ransomNote.length(); j++){
                if(magazine[i] == ransomNote[j]){
                    ransomNote.erase(ransomNote.begin() + j);
                    break;
                }
            }
        }
        if(!ransomNote.length()) return true;
        return false;
    }
};

//哈希解法 - 數組在哈希法中的應用
//時間複雜度O(n)
//空間複雜度O(1)
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26] = {0};
        
        for(char a : magazine) record[a - 'a']++;
    
        for(char a : ransomNote){
            record[a - 'a']--;
            if(record[a - 'a'] < 0) return false;
        }
        return true;
    }
};

//哈希法
//時間複雜度O(n^2)
 class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
// 宣告二維vector
        sort(nums.begin(),nums.end());
        
        for(int i = 0; i < nums.size(); i++){
            
            if(nums[i] > 0)
                continue;
            
            if(i > 0 && nums[i] == nums[i-1])
                continue;
            
            unordered_set<int> set;
            
            for(int j = i+1; j < nums.size(); j++){
                
                if(j > i+2 && nums[j] == nums[j-1] && nums[j-1] == nums[j-2])
                    continue;
                
                int c = 0 - (nums[i] + nums[j]);
                
                if(set.find(c) != set.end()){
                    result.push_back({nums[i], nums[j], c});
                         //push_back 插到最後面
                    set.erase(c);
//Q : unordered_set.erase(a) 是把所有a都清除嗎(假設容器裡面至少有2個a) 還是只刪一個?
//A : unordered_set中不存在重複的值
                }
                else set.insert(nums[j]);
            }
        }
        return result;
    }
};                                 
                                   

//雙指針法
//時間複雜度O(n^2)
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(),nums.end());
        
        for(int i = 0; i < nums.size(); i++){
            
            if(nums[i] > 0) return result;
            
            if(i > 0 && nums[i] == nums[i-1]) continue;
            
            int left = i + 1;
            int right = nums.size() - 1;
            
            while(right > left){
                if(nums[i] + nums[left] + nums[right] > 0) right--;
                else if (nums[i] + nums[left] + nums[right] < 0) left++;
                else {
                    result.push_back({nums[i], nums[left], nums[right]});
                    //    right > left && 易忘
                    while(right > left && nums[left] == nums[left + 1]) left++;
                    while(right > left && nums[right] == nums[right - 1]) right--;
                    right--;
                    left++;
                }
            }
        }
        return result;
    }
};

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size(); i++){
            if(i > 0 && nums[i]==nums[i-1])continue;
            
            int64_t t1 = target-nums[i]; // int64_t
            
            for(int j = i + 1; j < nums.size(); j++){
                if(j > i + 1 && nums[j]==nums[j-1])continue;
                
                int64_t t2 = t1-nums[j]; // int64_t
                
                int left = j + 1;
                int right = nums.size()-1;
                while(right > left){
    
                    // prevent int overflow
                    if(nums[left]+nums[right] > t2) right--;
                    else if(nums[left]+nums[right] < t2) left++;
                                                        
                    else{
                        result.push_back({nums[i], nums[j], nums[left], nums[right]});
                        while(right > left && nums[left] == nums[left + 1]) left++;
                        while(right > left && nums[right] == nums[right - 1]) right--;
                        right--;
                        left++;
                    }
                }
            }
        }
        return result;
    }
};

class Solution {
public:
    void reverseString(vector<char>& s) {
        for(int i = 0, j = s.size()-1; i < s.size()/2; i++,j--){
            swap(s[i],s[j]);
        }
    }
};

class Solution {
public:
    string reverseStr(string s, int k) {
        for(int i = 0; i < s.size(); i += 2*k){
            if(i + k <= s.size()){
                reverse(s.begin() + i, s.begin() + i + k);
                continue;
            }
            reverse(s.begin() + i, s.end());
        }
        return s;
    }
};                

class Solution {
public:
                                 
    //單字翻轉
    void reverse(string& s, int start, int end) {
        while(start < end){
            swap(s[start], s[end]);
            start++;
            end--;
        }
    }

    
    //去除多餘空白
    void removeExtraSpaces(string& s) {
        int slowIndex = 0, fastIndex = 0;
    
        // 去除字串前面的空格
        while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') 
            fastIndex++;
        
        for (; fastIndex < s.size(); fastIndex++) {
    
            // 去除字串中間部分的冗餘空格
            if (fastIndex - 1 > 0 &&
                s[fastIndex - 1] == s[fastIndex] && s[fastIndex] == ' ') 
                continue;
            else
                s[slowIndex++] = s[fastIndex];
        }
            
        if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') // 去除字串末的空格
            s.resize(slowIndex - 1);
        else
            s.resize(slowIndex); // 重新設定字串大小
    }
    
    string reverseWords(string s) {
        removeExtraSpaces(s);
        reverse(s, 0, s.size() - 1);
        int start, end = 0;
        bool entry = false;
        
        for (int i = 0; i < s.size(); i++) {

            if ((!entry) || (s[i] != ' ' && s[i - 1] == ' ')) {
                start = i;
                entry = true;
            }

            if (entry && s[i] == ' ' && s[i - 1] != ' ') {
                end = i - 1;
                entry = false;
                reverse(s, start, end);
            }
            
            if (entry && (i == (s.size() - 1)) && s[i] != ' ' ) {
                end = i;
                entry = false;
                reverse(s, start, end);
            }
        }
        return s;
    }
};                             

//KMP
//原始版前綴表 (沒有將整個表右移 或 -1)
                                     
class Solution {
public:
    
    void getNext(int* next, const string& s){
        
        int j = 0;
        next[0] = j;
        
        for(int i = 1; i < s.size(); i++){
            
            while(j > 0 && s[i] != s[j]) j = next[j-1];
            
            if (s[i] == s[j]) j++;
            
            next[i] = j;
        }
    }
//                    匹配字串          模式串
    int strStr(string haystack, string needle) {
        
        if(needle.size() == 0) return 0;
        
        int j = 0;
        int next[needle.size()];
        getNext(next, needle);
        
        for(int i = 0; i < haystack.size(); i++){
            
            while(j > 0 && haystack[i] != needle[j]) j = next[j-1];
            
            if(haystack[i] == needle[j]) j++;
            
            if(j == needle.size()) return i - needle.size() + 1; 
        }
        return -1;
    }
};

//前綴表
class Solution {
public:
    
    void getNext(int* next, const string& s){
        int j = 0;
        next[0] = j;
        for(int i = 1; i < s.size(); i++){
            while(j > 0 && s[i] != s[j]) j = next[j-1];
            if (s[i] == s[j]) j++;
            next[i] = j;
        }
    }
    
    bool repeatedSubstringPattern(string s) {
        
        int len = s.size();
        int next[len];
        getNext(next, s);
        /*  若 len % (len - next[len-1]) == 0 則 return True
               len可被len-s的長相等前後綴長度 整除   
                     len-s的長相等前後綴長度 為 最小重覆子字串長度
                12 %  (12-9)
            s = "abcabcabcabc"
        next[]=  000123456789
    
            s = "abab"
        next[]=  0012
            s = "abac"
        next[]=  0010
         最後一位不可為0
        */    
        if (len % (len - next[len-1]) == 0 && next[len - 1] != 0) return true;
        return false;
    }
};

    class MyQueue {
public:
    
    stack<int> stIn;
    stack<int> stOut;
    
    MyQueue() {
        
    }
    
    void push(int x) {
        stIn.push(x);
    }
    
    int pop() {
        if(stOut.empty()){
            while(!stIn.empty()){
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int temp = stOut.top();
        stOut.pop();
        return temp;
    }
    
    int peek() {
        int res = this->pop();
        stOut.push(res);
        return res;
    }
    
    bool empty() {
        return stIn.empty() && stOut.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

//用兩個stack實現 (一個用來備份
class MyStack {
public:
    
    queue<int> que1;
    queue<int> que2;
    
    MyStack() {
    
    }
    
    void push(int x) {
        que1.push(x);
    }
    
    int pop() {
        int size = que1.size();
        while(size != 1){
            que2.push(que1.front());
            que1.pop();
            size--;
        }
        
        int res = que1.front();
        que1 = que2;
        
        while(!que2.empty()) //clear que2
            que2.pop();
        
        return res;
    }
    
    int top() {
        return que1.back(); //last   X:front()
    }
    
    bool empty() {
        return que1.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */ 

//用一個stack實現 
class MyStack {
public:
    
    queue<int> que1;
    
    MyStack() {
        
    }
    
    void push(int x) {
        que1.push(x);
    }
    
    int pop() {
        int size = que1.size();
        while(size != 1){
            que1.push(que1.front());//把最後一個前面的push到它後面
            que1.pop();
            size--;
        }
        int res = que1.front();
        que1.pop();
        return res;
    }
    
    int top() {
        return que1.back(); 
    }
    
    bool empty() {
        return que1.empty();
    }
};

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '(') st.push(')');
            else if (s[i] == '[') st.push(']');
            else if (s[i] == '{') st.push('}');
            else if (st.empty() || s[i] != st.top()) return false;
            else st.pop();
        }
        return st.empty();
    }
};

class Solution {
public:
    string removeDuplicates(string S) {
        
        stack<char> st;
        
        for(char s:S){
            if(st.empty() || s != st.top()) st.push(s);
            else st.pop();
        }
        
        string res = "";
        while(!st.empty()){
            res += st.top();
            st.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};                      

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(int i = 0; i < tokens.size(); i++){
//                           v 不可用'
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){
                int num2 = st.top();
                st.pop();
                int num1 = st.top();
                st.pop();
                if(tokens[i] == "+") st.push(num1 + num2);
                if(tokens[i] == "-") st.push(num1 - num2);
                if(tokens[i] == "*") st.push(num1 * num2);
                if(tokens[i] == "/") st.push(num1 / num2);
                
            }else{
                st.push(stoi(tokens[i]));
            }
        }
        return st.top();
            
    }
};
/*
單調隊列，即單調遞減或單調遞增的隊列
*/

class Solution {
private:
    // 單調隊列，即單調遞減或單調遞增的隊列 (這邊使用單調遞增)
    class Mydeque{
        public:
            deque<int> que;
            
            void pop(int value){
                if(!que.empty() && value == que.front())
                    que.pop_front();
            }
        
            void push(int value){
                while(!que.empty() && value > que.back())
                    que.pop_back();
                
                que.push_back(value);
            }
        
            int front(){
                return que.front();
            }
    };
    
    
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        
        vector<int> result;
        Mydeque que;
        
        for(int i = 0; i < k;i++)
            que.push(nums[i]);
        
        
        for(int i = k; i < nums.size(); i++){
            result.push_back(que.front());
            que.pop(nums[i-k]);
            que.push(nums[i]);
        }
        
        result.push_back(que.front());
        return result;
    }
};

class Solution {
public:
    
    class cmp{
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs){
            return lhs.second > rhs.second;
        }
    };
    
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> map;
            
        for(int i = 0; i < nums.size(); i++)  // map<nums[i],出現次數>
            map[nums[i]]++;
        
            
        // priority_queue<T, vector<T>, cmp> pq; 自行定義 cmp 排序    
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
        
        for(unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++){
            pq.push(*it);
            if(pq.size() > k)
                pq.pop();
        }
        
        //                 v 設定容器大小為k
        vector<int> result(k);
        for(int i = k -1; i >= 0 ;i--){
//                               v 用.first 因為 儲存的元素是pair
            result[i] = pq.top().first;
            pq.pop();
        }
        
        return result;
        
    }
};
/*
什麼是優先級隊列(priority_queue)呢？
其實就是一個披著隊列外衣的堆，因為優先級隊列對外接口只是從隊頭取元素，
從隊尾添加元素，再無其他取元素的方式，看起來就是一個隊列。
而且優先級隊列內部元素是自動依照元素的權值排列。

如需改變priority_queue的優先權定義：
priority_queue<T> pq; 預設由大排到小
priority_queue<T, vector<T>, greater<T> > pq;  改成由小排到大
priority_queue<T, vector<T>, cmp> pq; 自行定義 cmp 排序            
*/

/*         
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
*/
class Solution {
public:
    
    void traversal(TreeNode* cur, vector<int>& vec){
        if (cur == NULL)return;
        vec.push_back(cur->val);
        traversal(cur->left, vec);
        traversal(cur->right, vec);
    }
    
    
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

/*
C++中map、set、multimap，multiset的底層實現都是平衡二叉搜索樹，所以map、set的增刪操作時間時間複雜度是logn，
unordered_map、unordered_map底層實現是哈希表。

二叉樹的定義
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
*/
            
//--------------------------------------------------------------------------
// nonrecursive
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if(!root) return result;
        st.push(root);
        while(!st.empty()){
            TreeNode* node = st.top();
            
            st.pop();
            result.push_back(node->val);
            if (node->right) st.push(node->right);
            if (node->left ) st.push(node->left);
        }
        return result; 
    }
};
            
//-------------------------------------------------------------------------- 
// 迭代法           
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if(root) st.push(root);
        while(!st.empty()){    
            TreeNode* node = st.top();
            if(node){
                st.pop();
                if(node->right) st.push(node->right);
                if(node->left) st.push(node->left);
                st.push(node);
                st.push(NULL); 
            }else{
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
        return result;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec){
        if(cur == NULL)return;
        traversal(cur->left, vec);
        traversal(cur->right, vec);
        vec.push_back(cur->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};
            
//--------------------------------------------------------------------------
// nonrecursive          
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if(!root) return result;
        st.push(root);
        while(!st.empty()){
            TreeNode* node = st.top();
            result.push_back(node->val);
            st.pop();
            if(node->left ) st.push(node->left);
            if(node->right) st.push(node->right);
        }
        reverse(result.begin(), result.end());
        return result;
    }
};
            
//-------------------------------------------------------------------------- 
// 迭代法          
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if(root) st.push(root);
        while(!st.empty()){    
            TreeNode* node = st.top();
            if(node){
                st.pop();
                st.push(node);
                st.push(NULL); 
                if(node->right) st.push(node->right);
                if(node->left) st.push(node->left);
            }else{
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
        return result;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec){
        if(cur == NULL)return;
        traversal(cur->left, vec);
        vec.push_back(cur->val);
        traversal(cur->right, vec);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};
            
//--------------------------------------------------------------------------      
// nonrecursive
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        TreeNode* cur = root;
        while(cur || !st.empty()){
            if(cur){
                st.push(cur);
                cur = cur->left;
            }else{
                cur = st.top();
                result.push_back(cur->val);
                st.pop();
                cur = cur->right;
            }
        }
        return result;
    }
};
            
//-------------------------------------------------------------------------- 
// 迭代法
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if(root) st.push(root);
        while(!st.empty()){    
            TreeNode* node = st.top();
            if(node){
                st.pop();
                if(node->right) st.push(node->right);
                st.push(node);
                st.push(NULL); 
                if(node->left) st.push(node->left);
            }else{
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
        return result;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> result;
        if(root) que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> vec;
            for(int i = 0; i < size; i++){
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};
            
//-------------------------------------------------------------------------- 
//Recursion
            
class Solution {
public:
    void order(TreeNode* cur, vector<vector<int>>& result, int depth){
        if(cur == nullptr)return;
        if(result.size() == depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth+1);
        order(cur->right, result, depth+1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};
            
// 相關題(9)
            

// 107.二叉樹的層次遍歷II
class Solution {
public:
    void order(TreeNode* cur, vector<vector<int>>& result, int depth){
        if(cur == nullptr)return;
        if(result.size() == depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth+1);
        order(cur->right, result, depth+1);
    }
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        reverse(result.begin(), result.end());
        return result;
    }
};

// 199.二叉樹的右視圖
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> que;
        vector<int> result;
        if(root) que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> vec;
            for(int i = 0; i < size; i++){
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            result.push_back(vec[vec.size()-1]);
        }
        return result;
    }
};
// 637.二叉樹的層平均值
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        queue<TreeNode*> que;
        vector<double> result;
        if(root) que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> vec;
            for(int i = 0; i < size; i++){
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            result.push_back(1.0 * accumulate(vec.begin(), vec.end(), 0) / vec.size());
        }
        return result;
    }
};

// 429.N叉樹的層序遍歷
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> result;
        if(!root)return result;
        queue<Node*> que;
        que.push(root);
        while(!que.empty()){
            vector<int> temp;
            int size = que.size();
            for(int i = 0; i < size; i++){
                Node* node = que.front();
                que.pop();
                temp.push_back(node->val);
                if (node->children.size() > 0)
                    for(auto child : node->children)
                        que.push(child);
            }
            result.push_back(temp);
        }
        return result;
    }
};

// 515.在每個樹行中找最大值
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> result;
        queue<TreeNode*> q;
        if(root) q.push(root);
        while(!q.empty()){
            int size = q.size();
            vector<int> temp;
            for(int i = 0; i < size; i++){
                TreeNode* cur = q.front();
                q.pop();
                temp.push_back(cur->val);
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
            result.push_back(*max_element(temp.begin(), temp.end()));
        }
        return result;
    }
};

// 116.填充每個節點的下一個右側節點指針
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        if(root and root->left){
            root->left->next = root->right;
            if(root->next) root->right->next = root->next->left;
            connect(root->left);
            connect(root->right);
        }
        return root;
    }
};

// 117.填充每個節點的下一個右側節點指針II
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return NULL;
        queue<Node*> q;
        q.push(root);
        while(!q.empty()){
            int n = q.size();
            for(int i = 0; i < n; i++){
                Node* temp = q.front();
                q.pop();
                if(i == n-1) temp->next = NULL;
                else temp->next = q.front();
                if(temp->left) q.push(temp->left);
                if(temp->right)q.push(temp->right);
            }
        }
        return root;
    }
};


// 104.二叉樹的最大深度
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        return max(left, right) + 1;
    }
};
//類似104  559. Maximum Depth of N-ary Tree
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    int maxDepth(Node* root) {
        int depth = 0;
        queue<Node*> q;
        if(!root) return 0;
        q.push(root);
        while(!q.empty()){
            int n = q.size();
            depth++;
            for(int i = 0; i < n; i++){
                Node* node = q.front(); q.pop();
                if(node->children.size())
                    for(auto child : node->children)
                        q.push(child);
            }
        }
        return depth;
    }
};   
//559 2
class Solution {
public:
    int maxDepth(Node* root) {
        int depth = 0;
        if(!root) return 0;
        if(root->children.size()){
            for(auto child : root->children)
                depth = max(depth, maxDepth(child));
        }
        return depth+1;
    }
};            
            
// 111.二叉樹的最小深度
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        int left = minDepth(root->left);
        int right = minDepth(root->right);
        if(!min(left, right)) return max(left, right) + 1;
        return min(left, right) + 1;
    }
};

            

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return root;
        swap(root->right, root->left);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};
            
//stack (in-order X)           
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return root;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()){
            TreeNode* node = st.top();
            st.pop();
            swap(node->right, node->left);
            if(node->right)st.push(node->right);
            if(node->left)st.push(node->left);
        }
        return root;
    }
};    
      
// stack (通用)            
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return root;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()){
            TreeNode* node = st.top();
            if(node){
                st.pop();
                if(node->right)st.push(node->right);
                if(node->left)st.push(node->left);
                st.push(node);
                st.push(NULL);
            }else{
                st.pop();
                node = st.top();
                st.pop();
                swap(node->right, node->left);
            }
        }
        return root;
    }
};            

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    
    bool cmp(TreeNode* left, TreeNode* right){
        if(!left && right) return false;
        else if(left && !right) return false;
        else if(left == right && !left) return true;
        else if(left->val != right->val) return false;
        
        bool in = cmp(left->right, right->left);
        bool out = cmp(left->left, right->right);
        return in && out;
    }
    
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return cmp(root->left, root->right);
    }
};
            
// 改
class Solution {
public:
    bool cmp(TreeNode* left, TreeNode* right){
        if(!left && !right) return true;
        else if(!right || !left || left->val != right->val) return false;
        return cmp(left->right, right->left) && cmp(left->left, right->right);
    }
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return cmp(root->left, root->right);
    }
};
            
// queue
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);
        while(!q.empty()){
            TreeNode* left = q.front(); q.pop();
            TreeNode* right = q.front(); q.pop();
            if(!left && !right) continue;
            if(!left || !right || left->val != right->val) return false;
            
            q.push(left->left);
            q.push(right->right);
            q.push(left->right);
            q.push(right->left);
        }
        return true;
    }
};   
            
// stack
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        stack<TreeNode*> st;
        st.push(root->right);
        st.push(root->left);
        while(!st.empty()){
            TreeNode* left = st.top(); st.pop();
            TreeNode* right = st.top(); st.pop();
            if(!left && !right) continue;
            if(!left || !right || left->val != right->val) return false;
            
            st.push(left->left);
            st.push(right->right);
            st.push(left->right);
            st.push(right->left);
        }
        return true;
    }
};
            
//100. Same Tree
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool cmp(TreeNode* p, TreeNode* q){
        if(!p && !q)return true;
        else if(!p || !q || p->val != q->val) return false;
        return cmp(p->right, q->right) && cmp(p->left, q->left);
    }
    
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p && !q) return true;
        return cmp(p, q);
    }
};     
            
//572. Subtree of Another Tree     
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */


class Solution {
public:
    
    bool cmp(TreeNode* p, TreeNode* q){
        if(!p && !q)return true;
        else if(!p || !q || p->val != q->val) return false;
        return cmp(p->right, q->right) && cmp(p->left, q->left);
    }
    
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if(!root) return false;
        return cmp(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
    }
};