Interviewbit/PostorderTraversal.cpp at master · jayakrishna-g/Interviewbit · GitHub

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
/*
Question:
Postorder Traversal
Asked in:
Amazon
Microsoft
Given a binary tree, return the postorder traversal of its nodes’ values.

Example :

Given binary tree

   1
    \
     2
    /
   3
return [3,2,1].

Using recursion is not allowed.

 */

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 *
 *
 */
 vector<int> ret;
void foo(TreeNode *root)
{
    if(root==NULL)
    return ;
    stack<TreeNode*> s;
    s.push(root);
    while(!s.empty())
    {
        TreeNode *n=s.top();
        s.pop();
        ret.push_back(n->val);
        if(n->left)
        s.push(n->left);
        if(n->right)
        s.push(n->right);
    }
}
vector<int> Solution::postorderTraversal(TreeNode* A) {
    ret.clear();
    foo(A);
    return ret;
}