曾是少年

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> his;
        vector<int> res;
        TreeNode *t = root, *dummy = new TreeNode(0);
        his.push(dummy);
        while(!his.empty()){
            while(t){
                res.push_back(t->val);
                his.push(t);
                t = t->left;
            }
            t = his.top()->right;
            his.pop();  
        }
        return res;
    }
};

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode *> st;
        if(root==nullptr)
            return res;
        st.push(root);
        while(!st.empty())
        {
            TreeNode* ptr = st.top();
            res.push_back(ptr->val);
            st.pop();
            if(ptr->right)
                st.push(ptr->right);
            if(ptr->left)
                st.push(ptr->left);
        }
        return res;
    }
};

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        cur = root
        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left
            top = stack.pop() #此时左子树遍历完成
            res.append(top.val)  #将父节点加入列表
            cur = top.right #遍历右子树
        return res

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = []
        cur = root
        while stack or cur:
            while cur:
                res.append(cur.val)
                stack.append(cur)
                cur = cur.right  #先将右节点压栈
            top = stack.pop()  #此时该节点的右子树已经全部遍历完
            cur = top.left  #对左子树遍历
        return res[::-1]  #结果翻转

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;  //保存结果
        stack<TreeNode*> st;  //调用栈
        if(root!=nullptr) st.push(root);  //首先介入root节点
        while(!st.empty()){
            TreeNode *t = st.top();
            st.pop();  //访问过的节点弹出
            if(t!=nullptr){
                if(t->right) st.push(t->right);  //右节点先压栈，最后处理
                if(t->left) st.push(t->left);
                st.push(t);  //当前节点重新压栈（留着以后处理），因为先序遍历所以最后压栈
                st.push(nullptr);  //在当前节点之前加入一个空节点表示已经访问过了
            }else{  //空节点表示之前已经访问过了，现在需要处理除了递归之外的内容
                res.push_back(st.top()->val);  //st.top()是nullptr之前压栈的一个节点，也就是上面st.push(t)中的那个t
                st.pop();  //处理完了，第二次弹出节点（彻底从栈中移除）
            }
        }
        return res;
    }
};