[ LeetCode ]前序、中序遍历二叉树

Binary Tree Preorder Traversal

//前序遍历二叉树
class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> res;
        if (root == NULL)
            return res;

        stack<TreeNode*> s;
        TreeNode* pCur = NULL;
        s.push(root);

        while (!s.empty())
        {
            pCur = s.top();
            s.pop();
            while (pCur)
            {
                res.push_back(pCur->val);
                if (pCur->left)
                    s.push(pCur->left);
                pCur = pCur->left;
            }
        }
        return res;
    }
};

Binary Tree Inorder Traversal

//中序遍历二叉树--非递归
class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> res;
        if (root == NULL)
            return res;

        stack<TreeNode*> s;
        TreeNode* pCur = root;
        TreeNode* pre = NULL;

        while (pCur || !s.empty())
        {
            if (pCur != NULL)//结点不为空，将结点压栈，并访问左子树
            {
                s.push(pCur);
                pCur = pCur->left;
            }
            else if (s.top()->right != pre)
            {
                pCur = s.top()->right;
                pre = NULL;
            }
            else
            {
                //访问右子树
                res.push_back(s.top()->val);
                pre = s.top();
                s.pop();
            }
        }
        return res;
    }
};