-
Notifications
You must be signed in to change notification settings - Fork 0
/
BinaryTreePostorderTraversal.hpp
69 lines (59 loc) · 1.2 KB
/
BinaryTreePostorderTraversal.hpp
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//Binary Tree Postorder Traversal
//
//Given a binary tree, return the postorder traversal of its nodes' values.
//
//For example :
//Given binary tree{ 1, #, 2, 3 },
//1
//\
//2
///
//3
//return[3, 2, 1].
//
//Note: Recursive solution is trivial, could you do it iteratively ?
#include <iostream>
#include <vector>
#include "Tree.hpp"
using namespace std;
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution
{
public:
vector<int> postorderTraversal(TreeNode* root)
{
std::vector<int> res;
if (nullptr == root)
return res;
std::vector<TreeNode*> que;
que.push_back(root);
typedef std::vector<TreeNode*>::iterator IT;
typedef std::vector<TreeNode*>::reverse_iterator RIT;
for (IT it = que.begin(); it != que.end(); it++)
{
if (nullptr != (*it)->left)
{
it = que.insert(it + 1, (*it)->left);
it = it - 1;
}
if (nullptr != (*it)->right)
{
it = que.insert(it + 1, (*it)->right);
it = it - 1;
}
}
for (RIT it = que.rbegin(); it != que.rend(); it++)
{
res.push_back((*it)->val);
}
return res;
}
};