LeetCode:二叉树先序中序后序的非递归版本

144. 二叉树的前序遍历

思路：先序遍历是第一次遍历到结点时，就对其进行处理。也就是先遍历当前结点，再遍历其左子树，进而右子树。那么在弹出当前结点时，应该先将其右子树压入栈中，再将其左子树压入栈。最终顺序为 当-左-右。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> v;
        if(!root)
            return v;
        stack<TreeNode *> s;
        s.push(root);
        while(!s.empty())
        {
            TreeNode *cur=s.top();  //取出当前结点
            v.push_back(cur->val);  //打印当前结点
            s.pop();   //弹出当前结点
            if(cur->right)  //压入当前结点右子树
                s.push(cur->right);
            if(cur->left)  //压入当前结点左子树
                s.push(cur->left);
        }
        return v;
    }
};

如果先压入左子树，再压入右子树，最终结果为 当-右-左。

94. 二叉树的中序遍历

思路：中序遍历为第二次遍历到结点时，对结点进行处理。这就要求先遍历到当前结点的左子树的叶结点，即当前结点非空，将当前结点压入栈中，并遍历其左结点。当前结点为空，取处栈顶元素，并打印，遍历栈顶元素的右结点。
（当前结点为栈顶结点的左结点，先遍历当前结点，再遍历栈顶，最后遍历栈顶的右，符合中序遍历。）

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
        if(!root)
            return v;
        stack<TreeNode *> s;
        TreeNode *cur=root;
        while(!s.empty()||cur!=NULL)
        {
            if(cur)  //当前结点非空
            {
                s.push(cur);
                cur=cur->left;
            }
            else  //当前结点为空
            {
                TreeNode *tmp=s.top(); //获取栈顶结点
                v.push_back(tmp->val);
                s.pop();  //对栈顶结点处理完成，弹出
                cur=tmp->right;  //遍历栈顶结点的右结点
            }
        }
        return v;
    }
};

145. 二叉树的后序遍历

思路：后序遍历实际上是第三次遍历到该结点才处理，但是用普通的栈只能遍历结点两次。因此可以再用一个辅助栈，利用先序遍历 当-左-右，改为 当-右-左，用栈反转即为 左-右-当，即后序遍历。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> v;
        if(!root)
            return v;
        stack<TreeNode *> s; //先序遍历的栈
        stack<TreeNode *> res; //反转用的栈
        s.push(root);
        while(!s.empty())
        {
            TreeNode *cur =s.top();
            res.push(cur);   //由先序遍历中的打印处理，变为压栈处理
            s.pop();
            if(cur->left)    //左先入栈 ，则左后出栈
                s.push(cur->left);
            if(cur->right)  ////右后入栈 ，则右先出栈
                s.push(cur->right);
        }
        while(!res.empty())  //此时res为 当-右-左 反转即可
        {
            TreeNode* tmp=res.top();
            v.push_back(tmp->val);
            res.pop();
        }
        return v;
    }
};