[LeetCode] Binary Tree Preorder Traversal & Binary Tree Postorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

Given a binary tree, return the postorder traversal of its nodes' values.

问题描述：给定一个二叉树，返回它的先序和后序遍历序列。

这里给的是先序和后序，中序遍历可以参考Binary Tree Inorder Traversal。

先来看先序，先序和中序类似，只是访问的顺序不太一样。

class Solution {
public:
    vector preorderTraversal(TreeNode *root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        stack sta;
        TreeNode *pnode = root;
        vector vec;

        while(pnode || !sta.empty()) {
            while(pnode) {
                vec.push_back(pnode->val);
                sta.push(pnode);
                pnode = pnode->left;
            }
            if(!sta.empty()) {
                pnode = sta.top();
                sta.pop();
                pnode = pnode->right;
            }
        }
        return vec;
    }
};

再来看看后序，后序相对复杂，主要复杂的地方在于，当获取栈顶节点的时候是否该访问它呢？也就是说，它的右孩子是否已经访问了呢？

因此，在后序遍历时，栈中的元素除了包含节点指针外，还包含一个标志节点是否访问的变量。下面的代码主要是参考二叉树的非递归后序遍历算法。

class Solution {
public:
    vector postorderTraversal(TreeNode *root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        stack<> > sta;
        TreeNode *pnode = root;
        vector vec;
        pair ptnode;

        //从根节点开始，往左下方走，一直走到头，将路径上的每个节点入栈
        while(pnode) {
            sta.push(make_pair(pnode, 0)); //压入栈的有两个信息，一是节点指针，二是其右节点是否被访问过
            pnode = pnode->left;
        }

        while(!sta.empty()) { //当栈非空时
            ptnode = sta.top(); //获取栈顶元素

            //若其右孩子已经被访问过，或是该元素没有右孩子，则由后序遍历的定义，此时就可以访问这个节点了
            if(!ptnode.first->right || ptnode.second) {
                ptnode = sta.top();
                sta.pop();
                vec.push_back(ptnode.first->val);
            }
            else { //若其右孩子存在且它的右孩子没有被访问过，就去处理其右孩子
                ptnode.second = 1;
                sta.pop();
                sta.push(ptnode);
                pnode = ptnode.first->right;
                while(pnode) {
                    sta.push(make_pair(pnode, 0));
                    pnode = pnode->left;
                }
            }
        }
        return vec;
    }
};

小结：

先序：在先序遍历的非递归遍历中，是先沿着左孩子一直遍历，边遍历边访问，然后压入栈中，直到节点为空，然后取栈顶元素，此时，由于它的左孩子在它之后入栈，可以断定，它本身和它的左孩子一定已经被访问过了，按照先序遍历的规则，于是将节点设置为右孩子，然后开始下一轮遍历，也就是说，现在可以访问右子树了。

中序：在中序遍历的非递归遍历中，也是先沿着左孩子一直遍历，但是此时并不访问，只是沿着左孩子将节点都压入栈中，直到当前节点为空，然后取栈顶元素，由于它的左孩子在它之后入栈，因此，当前栈顶节点的左孩子必定已经被访问过了，于是访问当前节点，然后将节点设置为右孩子，开始下一轮遍历。

后序：在后序遍历的非递归遍历中，也是先沿着左孩子，一直遍历，但是此时并不访问，而且在向栈中压入节点时，同时还要保存一个标志信息（标志该节点的右孩子是否被访问过）。然后取栈顶节点，因为栈顶节点的左孩子是在它之后入栈的，因此，它的左孩子一定已经被访问过了，根据后序遍历规则，此时，如果右孩子被访问了，则访问栈顶节点，那么，如何知道右孩子是否被访问了呢？就是之前保存在栈中的标志信息的作用了。如果栈顶节点没有右孩子或者它的右孩子已经被访问过了，此时，就应该访问栈顶节点，并将栈顶节点弹出；否则，就应该访问右子树，但是，在访问右子树之前，应该将当前栈顶节点的标志信息设为1（表示它的右子树已经访问了），然后访问右子树。于是，后序的非递归遍历也可以这样：

class Solution {
public:
    vector postorderTraversal(TreeNode *root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        stack<> > sta;
        TreeNode *pnode = root;
        vector vec;
        pair ptnode;

        while(pnode || !sta.empty()) {
            while(pnode) {
                sta.push(make_pair(pnode, 0));
                pnode = pnode->left;
            }
            if(!sta.empty()) {
                ptnode = sta.top();

                if(!ptnode.first->right || ptnode.second) {
                    sta.pop();
                    vec.push_back(ptnode.first->val);
                }
                else {
                    ptnode.second = 1;
                    sta.pop();
                    sta.push(ptnode);
                    pnode = ptnode.first->right;
                }
            }
        }
        return vec;
    }
};