# Question

Formatted question description: https://leetcode.ca/all/145.html

Given the root of a binary tree, return the postorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3]
Output: [3,2,1]


Example 2:

Input: root = []
Output: []


Example 3:

Input: root = [1]
Output: [1]


Constraints:

• The number of the nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Follow up: Recursive solution is trivial, could you do it iteratively?

# Algorithm

Since the order of post-order traversal is left-right-root, and the order of pre-order traversal is root-left-right, the two are actually very similar.

You can make some small changes in the method of pre-order traversal to make it work. The order becomes root-right-left, and then flipped, that is, left-right-root. The flip method is to add the result res in the reverse direction.

Each time, when adding to stack, left and then right, so that when the stack is processed, it is right and then left.

# Code

• import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Binary_Tree_Postorder_Traversal {

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution_two_stacks {
public List<Integer> postorderTraversal(TreeNode root) {

List<Integer> list = new ArrayList<>();

if (root == null) {
return list;
}

Stack<TreeNode> sk = new Stack<>();
Stack<TreeNode> reversedResult = new Stack<>();
sk.push(root);

while (!sk.isEmpty()) {
TreeNode current = sk.pop();

reversedResult.push(current);

// @note:@memorize: left first then right. why? - right will be popped out first
if (current.left != null) {
sk.push(current.left);
}
if (current.right != null) {
sk.push(current.right);
}

}

// reversed to natural order
while (!reversedResult.isEmpty()) {
}

return list;

}
}

public class Solution {
public List<Integer> postorderTraversal(TreeNode root) {

ArrayList<Integer> list = new ArrayList<Integer>();

// Check for empty tree
if (root == null) {
return list;
}

Stack<TreeNode> sk = new Stack<TreeNode>();
sk.push(root);
TreeNode prev = null;

while (!sk.isEmpty()) {
TreeNode current = sk.peek();

/*
* go down the tree in search of a leaf if so process it and
* pop stack otherwise move down
*/
if (prev == null || prev.left == current || prev.right == current) {
if (current.left != null) {
sk.push(current.left);
} else if (current.right != null) {
sk.push(current.right);
} else { // left node here
sk.pop();
}

/*
* go up the tree from left node, if the child is right push
* it onto stack otherwise process parent and pop stack
*/
} else if (current.left == prev) {
if (current.right != null) {
sk.push(current.right);
} else {
sk.pop();
}

/*
* go up the tree from right node and after coming back from
* right node process parent and pop stack
*/
} else if (current.right == prev) {
sk.pop();
}

prev = current;
}

return list;

}
}

}

############

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
while (root != null) {
if (root.right == null) {
root = root.left;
} else {
TreeNode next = root.right;
while (next.left != null && next.left != root) {
next = next.left;
}
if (next.left == null) {
next.left = root;
root = root.right;
} else {
next.left = null;
root = root.left;
}
}
}
return ans;
}
}

• // OJ: https://leetcode.com/problems/binary-tree-postorder-traversal/
// Time: O(N)
// Space: O(H)
class Solution {
private:
vector<int> ans;
void dfs(TreeNode* root) {
if (!root) return;
dfs(root->left);
dfs(root->right);
ans.push_back(root->val);
}
public:
vector<int> postorderTraversal(TreeNode* root) {
dfs(root);
return ans;
}
};

• # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
while root:
if root.right is None:
ans.append(root.val)
root = root.left
else:
next = root.right
while next.left and next.left != root:
next = next.left
if next.left != root:
ans.append(root.val)
next.left = root
root = root.right
else:
next.left = None
root = root.left
return ans[::-1]

############

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

class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res, stack = [], [(1, root)]
while stack:
p = stack.pop()
if not p[1]:
continue
if p[0] == 0:
res.append(p[1].val)
else:
stack.extend([(0, p[1]), (1, p[1].right), (1, p[1].left)])
return res


• /**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func postorderTraversal(root *TreeNode) []int {
var ans []int
for root != nil {
if root.Right == nil {
ans = append([]int{root.Val}, ans...)
root = root.Left
} else {
next := root.Right
for next.Left != nil && next.Left != root {
next = next.Left
}
if next.Left == nil {
ans = append([]int{root.Val}, ans...)
next.Left = root
root = root.Right
} else {
next.Left = nil
root = root.Left
}
}
}
return ans
}

• /**
* Definition for a binary tree node.
* class TreeNode {
*     val: number
*     left: TreeNode | null
*     right: TreeNode | null
*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.left = (left===undefined ? null : left)
*         this.right = (right===undefined ? null : right)
*     }
* }
*/

function postorderTraversal(root: TreeNode | null): number[] {
if (root == null) return [];
let stack = [];
let ans = [];
let prev = null;
while (root || stack.length) {
while (root) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (!root.right || root.right == prev) {
ans.push(root.val);
prev = root;
root = null;
} else {
stack.push(root);
root = root.right;
}
}
return ans;
}


• // Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, res: &mut Vec<i32>) {
if root.is_none() {
return;
}
let node = root.as_ref().unwrap().borrow();
Self::dfs(&node.left, res);
Self::dfs(&node.right, res);
res.push(node.val);
}

pub fn postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
let mut res = vec![];
Self::dfs(&root, &mut res);
res
}
}