【LeetCode】-- 145. 二叉树的后序遍历

简介: 【LeetCode】-- 145. 二叉树的后序遍历

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. };


相关文章
|
2月前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
20 2
|
2月前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
18 2
|
2月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
20 0
|
2月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
15 0
|
2月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
18 0
|
2月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
21 0
|
2月前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
19 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
59 6
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
121 2