题解 | #二叉树的后序遍历#

二叉树的中序遍历

http://www.nowcoder.com/practice/1b25a41f25f241228abd7eb9b768ab9b

总结二叉树的非递归遍历思路
非递归一般是用栈实现，那么就要明确栈是先入后出的原则。
1. 前序遍历

前序遍历要求的输出顺序是根、左、右，那么结合栈的特点，入栈顺序就应该是右、左、根的顺序。
程序编写的时候需要一个栈和一个辅助指针，辅助指针tmp记录当前节点，首先把辅助指针指向的当前节点入栈(相当于根节点入栈)，这样栈不为空的情况下，进行以下循环：弹出当前节点值(根)，放到返回数组res中，然后先在右子树不为空的时候入栈右子树，再在左子树不为空的时候入栈左子树，这样就可以保证栈顶元素弹出顺序为根、左、右。
图片说明

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> preorderTraversal(TreeNode* root) {
        // write code here
        vector<int> res;
        if(root==NULL)
        {
            return res;
        }
        stack<TreeNode*> TreeStack;
        TreeNode* tmp = root;
        TreeStack.push(tmp);
        while(TreeStack.size() > 0)
        {
            TreeNode* node = TreeStack.top();
            TreeStack.pop();
            res.push_back(node->val);
            if(node->right != NULL)
            {
                TreeStack.push(node->right);
            }
            if(node->left != NULL)
            {
                TreeStack.push(node->left);
            }
        }
        return res;
    }
};

2. 中序遍历

中序遍历要求的输出顺序是左、根、右，那么结合栈的特点，入栈顺序就应该是右、根、左的顺序。
程序编写的时候需要一个栈和2个辅助指针，一个辅助指针tmp记录当前节点，先将指针访问的数据入栈，一直访问其左孩子，直到将左孩子全部入栈；此时栈不为空，定义另一个辅助指针node指针，该指针指向栈顶元素，也就是最后一个左孩子。之后栈内有内容就取栈顶元素，放到返回数组中，同时每取一个栈顶元素，就把tmp指向其右孩子，这样就可以把根节点的左子树的所有左孩子，同时保证在有右孩子的情况下会将右孩子也入栈。然后又会在右孩子也有孩子的情况下再次遍历入栈，出栈的时候也会保证先左再中再右。
图片说明

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

//#include <vector>
//#include <stack>
//using namespace std;

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> inorderTraversal(TreeNode* root) {
        // write code here
        vector<int> res;//记录出栈数值
        stack<TreeNode*> Treestack;//定义栈Treestack，栈中类型为TreeNode*
        TreeNode* tmp = root;
        if(tmp == NULL)
        {
            return res;
        }

        while(Treestack.size() > 0 || tmp!=NULL)
        {
            while(tmp!=NULL)
            {
                Treestack.push(tmp);//左侧节点入栈
                tmp=tmp->left;
            }
            if(Treestack.size() > 0)
            {
                TreeNode* node = Treestack.top();//取栈顶元素
                Treestack.pop();//出栈
                res.push_back(node->val);
                tmp = node->right;
            }
        }
        return res;
    }
};

3. 后序遍历

后序遍历要求的输出顺序是左、右、根，那么结合栈的特点，入栈顺序就应该是根、右、左的顺序。
后序遍历是最复杂的，需要一个栈和2个辅助指针，一个辅助指针current记录当前节点，另一个辅助指针pre记录上一个访问的节点(或者叫上一个被弹出的节点)。
将根节点压入栈中，再遍历访问左子树的左孩子，并且压入栈中；之后弹栈顶元素，当前栈顶元素为整棵树最左边的节点，对于后序遍历，他一定是第一位，所以放到返回数组res里面，满足的前提条件首先有它是个叶子节点，也就是右孩子为空(为什么不强调左孩子，因为在进行弹出元素之前已经确定了它没有左孩子)。接下来就是用pre记录当前节点，将current置空，方面接受下一步。由于栈内仍有元素，那么大循环不结束，但此时current为空，不会压入当前节点的左孩子，而是继续取栈顶元素赋给current，此时current记录的就是前面pre的父节点，那么就要判断current有没有未被访问到的右孩子，也就是条件(current->right != NULL && current->right != pre),有的话就要将其压入栈，也就是current=current->right,这样可以保证栈中的顺序从下到上是父、右、左。

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> postorderTraversal(TreeNode* root) {
        // write code here
        vector<int> res;
        if(root == NULL)
        {
            return res;
        }
        stack<TreeNode*> TreeStack;
        TreeNode* current = root;//记录当前节点
        TreeNode* pre = NULL;//记录前一个节点
        while(TreeStack.size()>0 || current != NULL)
        {
            if(current != NULL)
            {
                TreeStack.push(current);
                current=current->left;
            }
            else
            {
                current=TreeStack.top();
                if(current->right != NULL && current->right != pre)
                {
                    current = current->right;
                }
                else
                {
                    TreeStack.pop();
                    res.push_back(current->val);
                    pre = current;
                    current = NULL;
                }
            }
        }
        return res;
    }
};

第二种方式
注意以下代码在牛客上直接提交会报内存超额，但是这样写便于理解，为了解决内存超额，可以把一些循环判断的条件进行改写。
如
22行改为 if(!current)
32行改为if(!node->left && !node->right)
40行改为
while(TreeStack.size()>0 && (pre->left || pre->right) && (pre->left==node || pre->right==node))
50行和52行分别改为
if(node->right)
if(node->left)

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> postorderTraversal(TreeNode* root) {
        // write code here
        TreeNode* current = root;
        TreeNode* pre = NULL;
        stack<TreeNode*> TreeStack;
        vector<int> res;
        if(current == NULL)
        {
            return res;
        }
        //根节点是最后被访问到，所以先入栈根节点
        TreeStack.push(current);
        //保证访问顺序是左右根，那么就要先入栈右节点
        while(TreeStack.size()>0)
        {
            TreeNode* node = TreeStack.top();//取栈顶元素判断
            if(node->left==NULL && node->right==NULL)
            {//说明node是叶子节点,要么是左节点，要么是右节点，
             //那么还需要判断node的前一个结点是不是栈顶结点的父节点
             //如果不是，只弹出node；如果是就要把父节点和node一起弹出。
             //不管是哪种情况，都要先弹node
                res.push_back(node->val);
                TreeStack.pop();
                pre = TreeStack.top();//取当前栈顶节点，判断pre是否是node的父节点
                while(TreeStack.size()>0 && (pre->left==NULL || pre->right==NULL) && (pre->left==node || pre->right==node))
                {//判断条件是要满足：栈不为空、当前栈顶有左右孩子，并且某一个孩子就是node
                    node = pre;
                    res.push_back(pre->val);
                    TreeStack.pop();
                    pre = TreeStack.top();
                }
            }
            else
            {//说明node有孩子，那么就要先入右孩子，再入左孩子
                if(node->right!=NULL)
                    TreeStack.push(node->right);
                if(node->left!=NULL)
                    TreeStack.push(node->left);
            }
        }
        return res;
    }
};

图解：
图片说明