题解 | #双栈实现非递归——二叉树的后序遍历#
二叉树的后序遍历
https://www.nowcoder.com/practice/1291064f4d5d4bdeaefbf0dd47d78541
/** * 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 */ //后序遍历的非递归方式,利用两个栈 s1,s2。s1,记录访问过的节点,s2记录的是后序遍历的倒序。 //根节点入栈S1,当栈S1非空时循环,S1栈顶元素出栈,并入栈S2,然后访问被出栈元素,若有左孩子,则左孩子入栈S1,若有右孩子,则右孩子入栈S1,栈S1为空时,栈S2所有元素依次出栈所得序列即为后序遍历序列 void post_order(TreeNode* Node,vector<int> &ans){ if(Node == NULL) return; stack<TreeNode *> s1; stack<TreeNode *> s2; s1.push(Node);//根节点入栈 while (!s1.empty()) { TreeNode *cur = s1.top(); s1.pop(); s2.push(cur); if(cur->left!=NULL) s1.push(cur->left); if(cur->right!=NULL) s1.push(cur->right); } //s2出栈的元素就是二叉树的后序遍历序列 while (!s2.empty()) { ans.push_back(s2.top()->val); s2.pop(); } } vector<int> postorderTraversal(TreeNode* root) { // write code here vector<int> ans; post_order(root, ans); return ans; } };