递归

void traverse(TreeNode *root) {
    if (root == nullptr) {
        return;
    }
    // 第一次来到当前节点打印, 则是前序
    traverse(root->left); // 离开当前节点, 前往左子树
    // 第二次来到当前节点打印, 则是中序
    traverse(root->right); // 离开当前节点, 前往右子树
    // 第三次来到当前节点打印, 则是后序
}

迭代

class Solution {
public:
    struct State {
        TreeNode *node;
        int count;
        State(TreeNode *node, int count) {
            this->node = node;
            // count == 0 表示递归的展开过程
            // count == 1 表示真正来到一个节点的时候 该怎么处理当前节点
            // 按照什么顺序处理 就是二叉树的什么序列
            this->count = count; 
        }
    }
    vector<int> preorderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return vector<int>();
        }
        stack<State> stk;
        stk.push(State(root, 0));
        vector<int> ans;
        while (!stk.empty()) {
            auto s = stk.top(); stk.pop();
            if (s.count == 1) {
                ans.push_back(s.node->val);
            } else {
                // 前序, 因为是入栈, 从下往上看入栈顺序是跟左右
                if (s.node->right) {
                    stk.push(State(s.node->right, 0));
                }
                if (s.node->left) {
                    stk.push(State(s.node->left, 0));
                }
                stk.push(State(s.node, 1));
                
//                // 中序
//                stk.push(State(s.node, 1));
//                if (s.node->right) {
//                    stk.push(State(s.node->right, 0));
//                }
//                stk.push(State(s.node, 1));
//                if (s.node->left) {
//                    stk.push(State(s.node->left, 0));
//                }
                
//                // 后序
//                stk.push(State(s.node, 1));
//                if (s.node->right) {
//                    stk.push(State(s.node->right, 0));
//                }
//                if (s.node->left) {
//                    stk.push(State(s.node->left, 0));
//                }
            }
        }
        return ans;
    }
};