# Binary Tree Postorder Traversal

## Question

### Problem Statement

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?

## 题解1 - 递归

### Python - Divide and Conquer

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
# @param {TreeNode} root
# @return {integer[]}
def postorderTraversal(self, root):
if root is None:
return []
else:
return self.postorderTraversal(root.left) +\
self.postorderTraversal(root.right) + [root.val]


### C++ - Traversal

/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/
class Solution {
/**
* @param root: The root of binary tree.
* @return: Postorder in vector which contains node values.
*/
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> result;

traverse(root, result);

return result;
}

private:
void traverse(TreeNode *root, vector<int> &ret) {
if (root == NULL) {
return;
}

traverse(root->left, ret);
traverse(root->right, ret);
ret.push_back(root->val);
}
};


### Java - Divide and Conquer

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
if (root != null) {
List<Integer> left = postorderTraversal(root.left);
List<Integer> right = postorderTraversal(root.right);
}

return result;
}
}


### Java - Traversal

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private List<Integer> result = new ArrayList<Integer>();

public List<Integer> postorderTraversal(TreeNode root) {
if (root != null) {
postorderTraversal(root.left);
postorderTraversal(root.right);
}
return result;
}
}


## 题解2 - 迭代

### 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 {TreeNode} root
# @return {integer[]}
def postorderTraversal(self, root):
result = []
if root is None:
return result
s = []
# previously traversed node
prev = None
s.append(root)
while s:
curr = s[-1]
noChild = curr.left is None and curr.right is None
childVisited = (prev is not None) and \
(curr.left == prev or curr.right == prev)
if noChild or childVisited:
result.append(curr.val)
s.pop()
prev = curr
else:
if curr.right is not None:
s.append(curr.right)
if curr.left is not None:
s.append(curr.left)

return result


### C++

/**
* 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) {
vector<int> result;
if (root == NULL) return result;

TreeNode *prev = NULL;
stack<TreeNode *> s;
s.push(root);
while (!s.empty()) {
TreeNode *curr = s.top();
bool noChild = false;
if (curr->left == NULL && curr->right == NULL) {
noChild = true;
}
bool childVisited = false;
if (prev != NULL && (curr->left == prev || curr->right == prev)) {
childVisited = true;
}

// traverse
if (noChild || childVisited) {
result.push_back(curr->val);
s.pop();
prev = curr;
} else {
if (curr->right != NULL) s.push(curr->right);
if (curr->left != NULL) s.push(curr->left);
}
}

return result;
}
};


### Java

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
Deque<TreeNode> stack = new ArrayDeque<TreeNode>();

if (root != null) stack.push(root);
TreeNode prev = null;
while (!stack.isEmpty()) {
TreeNode curr = stack.peek();
boolean noChild = (curr.left == null && curr.right == null);
boolean childVisited = false;
if (prev != null && (curr.left == prev || curr.right == prev)) {
childVisited = true;
}
if (noChild || childVisited) {
curr = stack.pop();
prev = curr;
} else {
if (curr.right != null) stack.push(curr.right);
if (curr.left != null) stack.push(curr.left);
}
}

return result;
}
}


## 题解3 - 反转先序遍历

### C++

/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/
class Solution {
/**
* @param root: The root of binary tree.
* @return: Postorder in vector which contains node values.
*/
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> result;
if (root == NULL) return result;

stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode *node = s.top();
s.pop();
result.push_back(node->val);
// root, right, left => left, right, root
if (node->left != NULL) s.push(node->left);
if (node->right != NULL) s.push(node->right);
}
// reverse
std::reverse(result.begin(), result.end());
return result;
}
};


### Java

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
if (root != null) stack.push(root);

while (!stack.isEmpty()) {
TreeNode curr = stack.pop();
if (curr.left != null) stack.push(curr.left);
if (curr.right != null) stack.push(curr.right);
}

Collections.reverse(result);
return result;
}
}