1. 题目
给你一棵二叉树的根节点
root，返回其节点值的 后序遍历 。
2. 示例
示例1：
输入：root = [1,null,2,3]
输出：[3,2,1]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
3. 分析
1.左右子树都访问完毕后，才能访问根
2.如何知道一个节点的左右子树都访问完了呢？用指针记录上一个访问的节点，如果上一个访问的节点恰好是节点的右子树的根，那么说明左右子树都已经访问完了，现在就可以访问节点了
4. 代码实现
1. /** 2. * Definition for a binary tree node. 3. * struct TreeNode { 4. * int val; 5. * TreeNode *left; 6. * TreeNode *right; 7. * TreeNode() : val(0), left(nullptr), right(nullptr) {} 8. * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} 9. * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} 10. * }; 11. */ 12. class Solution { 13. public: 14. vector<int> postorderTraversal(TreeNode* root) { 15. stack<TreeNode*> st; 16. vector<int> ret; 17. TreeNode* cur = root; 18. 19. TreeNode* prev = nullptr; 20. 21. while(cur || !st.empty()) 22. { 23. //左路节点保存到栈 24. while(cur) 25. { 26. st.push(cur); 27. cur = cur->left; 28. } 29. 30. //取一个栈顶元素，它的左路节点已经访问完了， 31. //如果它的右为空，或者右子树已经访问完了（上一个访问的节点是top的右子树），那么现在就可以访问右子树 32. TreeNode* top = st.top(); 33. if(top->right == prev || top->right == nullptr) 34. { 35. st.pop(); 36. ret.push_back(top->val); 37. prev = top; 38. } 39. else 40. { 41. cur = top->right; 42. } 43. } 44. 45. return ret; 46. } 47. };
