题意理解
如题
问题分析
递归解法
非递归解法
用栈，再用一个指示上一个访问节点，用于根节点判断是否已经回退还是访问右子树。
大思路是，向左走到底 -- 如果右子树存在，向右一步走 -- 先左走到底。
其中，如果右子树不存在，或者右子树存在但是被访问过了，访问当前节点，再回退上一个结点（弹栈即可）。
为了标记右子树是否被访问，可以看上一次访问的是否是自己的右孩子，如果是右孩子，表明访问过了，如果不是右孩子，表明没有被访问过。
其他
链接
vector<int> postorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> st; if (root == nullptr) { //空树 return res; //直接返回空序列 } TreeNode* p = root; while (p) { //初始化，向左走到最左节点 st.push(p); p = p -> left; } TreeNode* last_visited; //记录上一个别访问节点 while (!st.empty()) { //栈不空 p = st.top(); //弹出最左节点 st.pop(); if (p -> right == nullptr || last_visited == p -> right) { //左子树必为空，当右子树为空，或者右节点是上一个被访问节点（右子树访问完） res.push_back(p -> val); //输出当前节点 last_visited = p; //重置上一次访问节点 } else { //右子树存在 st.push(p); //再把当前节点入栈 p = p -> right; //向右一步 while (p) { //向左走到底（为下一循环做准备) st.push(p); p = p -> left; } } } return res; } vector<int> postorderTraversal(TreeNode* root) { if (!root) { return vector<int>{}; } vector<int> res{}; vector<int> l_vector = postorderTraversal (root -> left); //左子树的后序遍历 vector<int> r_vector = postorderTraversal (root -> right); //右子树的后序遍历 res.insert (res.end(), l_vector.begin(), l_vector.end()); //插入左子树遍历结果 res.insert (res.end(), r_vector.begin(), r_vector.end()); //插入右子树遍历结果 res.push_back (root -> val); //插入根 return res; }vector<int> postorderTraversal(TreeNode* root) { vector<int> res; if (root == nullptr) { return res; } stack<TreeNode*> st1; //存节点 stack<int> st2; //存倒过来的后序序列 st1.push(root); //入根节点 while (!st1.empty()) { //栈不空 TreeNode* p = st1.top(); //出栈， st2.push(p -> val); //拨开节点内的值 st1.pop(); //入后序序列栈 if (p -> left) st1.push(p -> left); //根处理完了，先入栈左节点 if (p -> right) st1.push(p -> right); //再入栈右节点，因为后序是先左后右再根，入第一个栈是先左后右，入第二个栈变成了先右后左，最后输出的时候就又变回先左后右了 } while (!st2.empty()) { res.push_back(st2.top()); st2.pop(); } return res; }
