Keshawn_lu's Blog

Leetcode 145. 二叉树的后序遍历

字数统计: 318阅读时长: 1 min
2020/09/29 Share

题目简介:

给定一个二叉树,返回它的 后序 遍历。

示例:

1
2
3
4
5
6
7
8
输入: [1,null,2,3]  
1
\
2
/
3

输出: [3,2,1]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

思路:

递归的算法就不说了,很熟练了。

说说迭代的方法,也就是把递归栈显式的表达出来。这时需要将处理的节点放入栈之后,紧接着放入一个空指针作为标记。

这种方法对于前中后序遍历都可用,只需交换次序即可。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
* 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) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {

if(!root)
return {};

vector<int> res;
stack<TreeNode*> stk;

stk.push(root);

while(!stk.empty()){

TreeNode* node = stk.top();

if(node != NULL){ //不能用!node

//stk.pop();
//stk.push(node); 后序可不加

stk.push(NULL); //加入标记

if(node -> right)
stk.push(node -> right);

if(node -> left)
stk.push(node -> left); //加入时为中右左,出来时为左右中
}
else{

stk.pop(); //弹出NULL
res.push_back(stk.top() -> val);
stk.pop();
}
}

return res;
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: