## Binary Tree Postorder Traversal (iteration)

Given a binary tree, return the

*postorder*traversal of its nodes' values.
For example:

Given binary tree

Given binary tree

`{1,#,2,3}`

,1 \ 2 / 3

return

`[3,2,1]`

.**Note:**Recursive solution is trivial, could you do it iteratively?

### Analysis:

Classical problem, the recursion version of the solution can be easily found by modifying here. In this post, I solved it iteratively. Which data structure do remind us ? Yes! Still stack!The algorithm has following steps, which is slight different from the previous question:

(1) Push the root node into the stack.

(2) while the stack is not empty, do:

**if**

the top node is a leaf node (no left&right children), pop it.

**or if**the top node has been visited, pop it. (here we use a sign head to show the latest popped node, if the top node's child = the latest popped node, either left or right, it must has been visited.)

**else**

b. push the right child of the top node (if exists)

c. push the left child of the top node (if exists)

### Code (C++):

/** * Definition for binary tree * 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) { stack<TreeNode*> st; vector<int> res; if (!root){return res;} st.push(root); TreeNode* head=root; while (!st.empty()){ TreeNode* top = st.top(); if ((top->left==NULL && top->right==NULL)||top->right==head || top->left==head){ res.push_back(top->val); st.pop(); head = top; }else{ if (top->right!=NULL){st.push(top->right);} if (top->left!=NULL){st.push(top->left);} } } return res; } };

### Code(Python):

# Definition for a binary tree node # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # @param root, a tree node # @return a list of integers def postorderTraversal(self, root): res = [] st = [] if root != None: st.append([root,False]) while len(st) != 0: tmp = st[-1] if tmp[1] == True: res.append(st.pop()[0].val) elif tmp[0].left == None and tmp[0].right == None: res.append(st.pop()[0].val) else: st[-1][1] = True if tmp[0].right != None: st.append([tmp[0].right, False]) if tmp[0].left != None: st.append([tmp[0].left, False]) return res

So in my understanding, you will return a stack? So basically you are using 2 stacks like this one: http://www.geeksforgeeks.org/iterative-postorder-traversal?

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteHere is my method (Recursive + Iterative + Morris )

ReplyDeletehttps://techgeekyan.blogspot.ca/2017/08/leetcode-145-binary-tree-postorder.html