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

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <stack>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型vector
     */
    vector<int> postorderTraversal(TreeNode* root) {
        // write code here
        stack<TreeNode*> Node;
        vector<int> order;
        while (root != nullptr || !Node.empty()) {
            while (root != nullptr) {
                Node.push(root);
                if(root->left!=nullptr)
                    root = root->left;
                else
                    root = root->right;
            }
            root = Node.top();
            Node.pop();
            order.push_back(root->val);
            if (!Node.empty()&&Node.top()->right != nullptr && Node.top()->left == root)
                root = Node.top()->right;
            else
                root = nullptr;
            }
            return order;
        }
};

后序遍历的非递归真的好难啊呜呜呜呜呜，看了三遍模板才写出来。

整个思路就是，如果当前节点非空，就放入栈，然后看看左边能不能往下，如果左边到头了就往右边，直到当前节点为空，也就是右边也到头了。这个时候栈里面存的就是最左边结点的右节点，也就是此时需要输出的位置（这里要注意，后序是左右根，对于最左结点来说，自己是根，如果他自己还有右节点，那需要先输出他的右结点，再输出他自己）。

将该节点从栈中弹出，作为新的root。

后面是一个比较绕的逻辑，我们现在面临的一个问题是，从当前这个弹出的root结点已经处理完了，下面回到此时的栈顶的节点，但是现在回到这个栈顶结点，是因为左边遍历完了回来的，还是因为右边遍历完了回来的，这两者的区别在于处理完当前的root，是找栈顶结点的右子树，还是root自己就是栈顶结点右子树，结束了需要直接处理此时的栈顶结点？

如果是第一种情况，也就是root是栈顶结点的左子树，那么将root赋值为Node.top()->right.如果是第二种情况，直接将root置为空，即可进入下次循环，回到上面直接处理栈顶结点的逻辑（打印栈顶结点值，将栈顶pop）