LeetCode —— 145. 二叉树的后序遍历
😶🌫️😶🌫️😶🌫️😶🌫️Take your time ! 😶🌫️😶🌫️😶🌫️😶🌫️
💥个人主页：🔥🔥🔥大魔王🔥🔥🔥
💥所属专栏：🔥魔王的修炼之路–力扣🔥
如果你觉得这篇文章对你有帮助，请在文章结尾处留下你的点赞👍和关注💖，支持一下博主。同时记得收藏✨这篇文章，方便以后重新阅读。
LeetCode —— 145. 二叉树的后序遍历
LeetCode —— 145. 二叉树的后序遍历
题目：给你一棵二叉树的根节点 root ，返回其节点值的后序遍历。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*///自己没做出来原因：前中序都做出来了是因为不用记录 pre 来判断何时访问根节点，因为后序会两次访问根节点，所以需要记录 pre 来判断是否其右子树访问玩了。自己因为找错了记录 pre 的时机，所以怎么也想不通，反正还是没看之前写的之前，自己的思路不行，想不出来具体的过程！当然这说的方法2，方法1就不用说了，是一个规律，自己做的时候都没想到还有两个栈的方法。// //递归
// class Solution {
// public:
// void PostOrder(TreeNode* root, vector<int>& v)
// {
// if(root == nullptr)
// return;
// PostOrder(root->left, v);
// PostOrder(root->right, v);
// v.push_back(root->val);
// }// vector<int> postorderTraversal(TreeNode* root) {
// vector<int> v;
// PostOrder(root, v);
// return v;
// }
// };//后序非递归：两个方法//方法1：建立两个栈，先按照 根，左，右 的顺序将节点压入第一个栈（压根的左右时先把根出掉），出掉的元素压入第二个栈，最后等第一个栈为空，//将第二个栈的元素弹出就是后序。说白了就是按 根，左，右 的顺序压入第二个栈，然后依次pop//方法2：建立一个栈，但是需要有标记，因为会经过两次根节点，如果不能判断是哪一次，那么就不知道到时候是该弹出还是该访问其子树。// //方法1:两个栈
// class Solution {
// public:
// vector<int> postorderTraversal(TreeNode* root)
// {
// stack<TreeNode*> st1;
// stack<TreeNode*> st2;
// vector<int> v;
// if(root == nullptr)
// return v;
// st1.push(root);
// while(!st1.empty())
// {
// TreeNode* tmp_node = st1.top();
// st1.pop();
// if(tmp_node->left)
// st1.push(tmp_node->left);
// if(tmp_node->right)
// st1.push(tmp_node->right);
// st2.push(tmp_node);
// }// while(!st2.empty())
// {
// TreeNode* tmp_node = st2.top();
// v.push_back(tmp_node->val);
// st2.pop();
// }
// return v;
// }
// };//方法2：1个栈,做标记：通过判断 pre 是否等于 cur(即top)->right。应该只能判断右边，不然很多情况都联系不起来，因为左右根，访问根之前肯定是刚访问了其右节点，所以肯定跟右边有关系，与左边很多情况联系不起来。
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> v;TreeNode* current = root;TreeNode* prev = nullptr;if(root == nullptr)return v;while(current || st.size()){while(current){st.push(current);current = current->left;}current = st.top();if(current->right != nullptr && prev != current->right){current = current->right;//prev = current;//这个按逻辑是不写的，真写上也没错，因为 prev 的作用就是判断 cur->right 是否等于 pre，在走到 cur 的时候，它的 pre 肯定是刚才 else 里更新的：cur->right 刚弹出，那么 prev 肯定最新赋值的是 cur->right。}else{v.push_back(current->val);prev = st.top();//prev只有在这被标记有用，每次右节点弹出时记录该右节点（其左子树已经没了，因为先走的左边），然后就会回到根，判断根的右节点就是我们刚刚走过（pop的）是否相等，相等就说明右边走过了，那么就该访问这个根。st.pop();//弹出这方面会越界吗？//若栈存储 node 对象（stack<node>）：deque 的 pop 操作会调用 node 的析构函数，直接销毁对象，导致树结构破坏。若栈存储 node* 指针（stack<node*>）：pop 仅移除指针，不触发任何对象析构，树结构安全。current = nullptr;//这不给空的话就不会终止循环，因为current永远都指向其中的节点，就是节点弹出了，但是对current不产生影响，它还是指向弹出指针指向的树的那块空间。但是如果 while 循环的时候不管 cur 的话，第一次又进不去循环。}}return v;}
};
- 博主长期更新，博主的目标是不断提升阅读体验和内容质量，如果你喜欢博主的文章，请点个赞或者关注博主支持一波，我会更加努力的为你呈现精彩的内容。
🌈专栏推荐
😈魔王的修炼之路–C语言
😈魔王的修炼之路–数据结构
😈魔王的修炼之路–C++
😈魔王的修炼之路–QT
😈魔王的修炼之路–算法
😈魔王的修炼之路–力扣
😈魔王的修炼之路–牛客
😈魔王的修炼之路–剑指offer
😈魔王的修炼之路–Linux
更新不易，希望得到友友的三连支持一波。收藏这篇文章，意味着你将永久拥有它，无论何时何地，都可以立即找到重新阅读；关注博主，意味着无论何时何地，博主将永久和你一起学习进步，为你带来有价值的内容。
