145. Binary Tree Postorder Traversal

# Hard, DFS

Solution 1: Recursive

Same logic as inorder and preorder binary traversal.

Java

// Some code
class Solution {
    ArrayList<Integer> res = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null)
            return res;
        
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        res.add(root.val);
        return res;
    }
}

Python

# 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 traversal(self, root, result):
        if root == None:
            return
        
        self.traversal(root.left, result)
        self.traversal(root.right, result)
        result.append(root.val)
        
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        # condier edge case
        result = []
        if root == None:
            return result
        
        # regular case
        self.traversal(root, result)
        return result

Solution 2: Divide & Conquer

Same logica as preorder and inorder binary traversal.

# 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: TreeNode) -> List[int]:
        # consider edge case
        result = []
        if root == None:
            return result
        
        # regular case
        # divide
        left = self.postorderTraversal(root.left)
        right = self.postorderTraversal(root.right)
        
        # conquer
        result.extend(left)
        result.extend(right)
        result.append(root.val)
        
        return result

Solution 3. Iterative(While-loop)

Use while-loop to find the most left node, adding them into the stack , remark those nodes as False at the same time( False means this node' right subtree hasn't been visited). Pop the most left node, if the node has been marked as True(the right subtree has been visited), then this node is root, add to res and put current ptr to None(in order to get parent node). Otherwise mark this node as visited, then push all the right subtree into the stack.

This is most efficient method.

Java (interesting method)

// Some code
class Solution {
  public List<Integer> postorderTraversal(TreeNode root) {
    if (root == null)
      return new ArrayList<>();

    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
      root = stack.pop();
      ans.add(root.val);
      if (root.left != null)
        stack.push(root.left);
      if (root.right != null)
        stack.push(root.right);
    }

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

Python

# 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: TreeNode) -> List[int]:
        res = []
        stack = []
        
        while root != None or len(stack) != 0:
            while root != None:
                stack.append([root, False])
                root = root.left
            tmp = stack.pop()
            root = tmp[0]
            if tmp[1] == True:
                res.append(tmp[0].val)
                root = None
            else:
                tmp[1] = True
                stack.append(tmp)
                root = root.right
                
        return res