题解 | #实现二叉树先序，中序和后序遍历#

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */


struct Info {
    TreeNode* ptr;
    int pos;
};

/*
void dfs(TreeNode* u) {
    // 1
    dfs(u->left);
    // 2
    dfs(u->right);
    // 3
}
*/

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > threeOrders(TreeNode* root) {
        // write code here
        vector<vector<int>> path(3);
        if (root == nullptr) return std::move(path);
        stack<Info> sk;
        sk.push({root, 1});
        while (!sk.empty()) {
            if (sk.top().pos == 1) {
                path[0].push_back(sk.top().ptr->val); // 前序遍历
                auto u = sk.top().ptr;
                auto cl = u->left;
                sk.top().pos = 2;
                if (cl != nullptr) { // 左子树不为空，那么递归访问左子树
                    sk.push({cl, 1});
                    continue;
                }
            }
            if (sk.top().pos == 2) {
                path[1].push_back(sk.top().ptr->val); // 中序遍历
                auto u = sk.top().ptr;
                auto cr = u->right;
                sk.top().pos = 3;
                if (cr != nullptr) { // 左子树不为空，那么递归访问左子树
                    sk.push({cr, 1});
                    continue;
                }
            }
            if (sk.top().pos == 3) {
                path[2].push_back(sk.top().ptr->val); // 后序遍历
                sk.pop();
            }
        }
        return std::move(path);
    }
};