vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> ret;
    if (root == NULL) return ret;

    queue<TreeNode*> que;
    que.push(root);
    while (!que.empty()) {
        int counter = que.size();
        vector<int> cur_row;
        while (counter--) {
            TreeNode* cur = que.front();
            que.pop();
            cur_row.push_back(cur->val);
            if (cur->left) que.push(cur->left);
            if (cur->right) que.push(cur->right);
        }
        ret.push_back(cur_row);
    }
    return ret;
}

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> ret;
    if (root == NULL) return ret;

    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* cur = st.top();
        st.pop();
        ret.push_back(cur->val);
        if (cur->right) st.push(cur->right);
        if (cur->left) st.push(cur->left);
    }
    return ret;
}

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ret;
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        if (cur) {
            st.push(cur);
            cur = cur->left;
        }
        else {
            cur = st.top();
            st.pop();
            ret.push_back(cur->val);
            cur = cur->right;
        }
    }
    return ret;
}

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ret;
    if (root == NULL) return ret;

    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* cur = st.top();
        st.pop();
        ret.push_back(cur->val);
        if (cur->left) st.push(cur->left);
        if (cur->right) st.push(cur->right);
    }

    reverse(ret.begin(), ret.end());
    return ret;
}

void bubbleSort(vector<int>& vec) {
    int n = vec.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (vec[j + 1] < vec[j]) swap(vec[j + 1], vec[j]);
        }
    }
}

void insertSort(vector<int>& vec) {
	for (int i = 1; i < vec.size(); i++) {
		int cur = vec[i];
		for (int j = i - 1; j >= 0; j--) {
			if (vec[j] > vec[j + 1]) 
                swap(vec[j + 1], vec[j]);
			else break;
		}
	}
}

void selectSort(vector<int>& vec) {
	for (int i = 0; i < vec.size(); i++) {
		int temp_min = vec[i], temp_min_idx = i;
		for (int j = i + 1; j < vec.size(); j++) {
			if (vec[j] < temp_min) {
				temp_min = vec[j];
				temp_min_idx = j;
			}
		}
		swap(vec[i], vec[temp_min_idx]);
	}
}

// 版本1：快慢指针，从左往右遍历
void quick_sort1(vector<int>& vec, int left, int right) {
	if (left >= right) return;
	
	int ptr = left, pivot = vec[ptr];
	for (int i = left + 1; i <= right; i++) {
		if (vec[i] < pivot) {
			ptr ++;
			swap(vec[ptr], vec[i]);
		}
	}
	swap(vec[left], vec[ptr]);

	quick_sort1(vec, left, ptr - 1);
	quick_sort1(vec, ptr + 1, right);

}

// 版本2：前后指针，最经典的方法
void quick_sort2(vector<int>& vec, int left, int right) {
	if (left >= right) return;

	int pivot = vec[left];
	int l = left, r = right;
	while (left < right) {
		while (left < right && vec[right] >= pivot) right --;
		while (left < right && vec[left] <= pivot) left ++;
		swap(vec[left], vec[right]);
	}
	swap(vec[left], vec[l]);

	quick_sort2(vec, l, left - 1);
	quick_sort2(vec, left + 1, r);
}

void quickSort(vector<int>& vec) {
	quick_sort2(vec, 0, vec.size() - 1);
}

void merge_sort(vector<int>& vec, int left, int right) {
	if (right <= left) return;

	int mid = left + (right - left) / 2;
	merge_sort(vec, left, mid);
	merge_sort(vec, mid + 1, right);

	int ptr1 = left, ptr2 = mid + 1;
	vector<int> temp;
	while (ptr1 <= mid && ptr2 <= right) {
		if (vec[ptr1] <= vec[ptr2]) {
			temp.push_back(vec[ptr1]);
			ptr1 ++;
		}
		else {
			temp.push_back(vec[ptr2]);
			ptr2 ++;
		}
	}
	while (ptr1 <= mid) temp.push_back(vec[ptr1++]);
	while (ptr2 <= right) temp.push_back(vec[ptr2++]);
	for (int i = 0; i < temp.size(); i++) {
		vec[left + i] = temp[i];
	}
}

void mergeSort(vector<int>& vec) {
	merge_sort(vec, 0, vec.size() - 1);
}

int gcd(int a, int b) {
	if (a < b) { a = a ^ b; b = a ^ b; a = a ^ b; }
    return b == 0 ? a : gcd(b, a % b);
}

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

class Trie {
private:
    // 定义前缀树结构体，有两个成员变量
    // isEnd：表示是否存在从根节点到当前节点的字符串
    // children：表示当前节点的26个子节点
    struct TrieNode {
        TrieNode() : isEnd(false), children(26, nullptr) {}
        ~TrieNode() {
            for (auto child : children) 
                if (child) delete child;
        }

        bool isEnd;
        vector<TrieNode*> children;
    };

    // 定义根节点
    TrieNode *root;
    
public:
    /** Initialize your data structure here. */
    Trie() : root(new TrieNode()) {}
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        TrieNode* cur = root;
        for (auto ch : word) {
            if (cur->children[ch - 'a'] == nullptr) {
                cur->children[ch - 'a'] = new TrieNode();
            }
            cur = cur->children[ch - 'a'];
        }
        cur->isEnd = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        TrieNode* cur = root;
        for (auto ch : word) {
            if (cur->children[ch - 'a'] == nullptr) return false;
            cur = cur->children[ch - 'a'];
        }
        return cur->isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        TrieNode* cur = root;
        for (auto ch : prefix) {
            if (cur->children[ch - 'a'] == nullptr) return false;
            cur = cur->children[ch - 'a'];
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */