二叉树非递归遍历

[GH1995]

class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> result;
        stack<TreeNode *> stk;

        auto cur = root;
        while (cur || !stk.empty()) {
            while (cur) {
                result.push_back(cur->val);
                stk.push(cur);
                cur = cur->left;
            }
            cur = stk.top(), stk.pop();
            cur = cur->right;
        }
        return result;
    }

    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> result;
        stack<TreeNode *> stk;

        auto cur = root;
        while (cur || !stk.empty()) {
            while (cur) {
                stk.push(cur);
                cur = cur->left;
            }
            cur = stk.top(), stk.pop();
            result.push_back(cur->val);
            cur = cur->right;
        }

        return result;
    }

    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> result;
        stack<TreeNode *> stk;

        auto cur = root;
        while (!stk.empty() || cur) {
            if (cur) {
                stk.push(cur);
                result.insert(result.begin(), cur->val);
                cur = cur->right;
            } else {
                cur = stk.top();
                stk.pop();
                cur = cur->left;
            }
        }

        return result;
    }
};