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

    	int low = left;
    	int high = right;

    	int key = arr[left];
    	while (left < right) {
    		while (left < right && arr[right] >= key) right--;
    		arr[left] = arr[right];
    		while (left < right && arr[left] <= key) left++;
    		arr[right] = arr[left];
    	}
    	arr[left] = key;
    	QSort(arr, low, left - 1);
    	QSort(arr, left + 1, high);
    }

class Solution {
public:
    // 前序，根左右
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        if (root == nullptr) return ans;

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

        return ans;
    }

    // 中序，左根右
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        if (root == nullptr) return ans;

        stack<TreeNode*> s;
        TreeNode* node = root;
        while (node || !s.empty()) {
            while (node) {
                s.push(node);
                node = node->left;
            }
            node = s.top();
            s.pop();
            ans.push_back(node->val);
            node = node->right;
        }
        return ans;
    }

    // 后续，根右左的逆序
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        if (root == nullptr) return ans;

        stack<TreeNode*> s;
        s.push(root);
        while (!s.empty()) {
            TreeNode* node = s.top();
            s.pop();
            ans.push_back(node->val);
            if (node->left) s.push(node->left);
            if (node->right) s.push(node->right);
        }
        reverse(ans.begin(), ans.end());

        return ans;
    }
};