# 145. Binary Tree Postorder Traversal
#### Difficulty: Easy
link: https://leetcode.com/problems/binary-tree-postorder-traversal/

### 1. Recursive method
#### $O(n)$ runtime, $O(n)$ space

##### 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: Optional[TreeNode]) -> List[int]:
        result = []
        def postorder(node):
            if node is not None:
                postorder(node.left)
                postorder(node.right)
                result.append(node.val)
        
        postorder(root)
        return result

### 2. Iterative method with Stack
#### $O(n)$ runtime, $O(n)$ space

postorder的順序是LRD(L: left child, R: right child, D: data)，把preorder做法內left和right的順序調換過來，可以取得DRL，反序以後得到postorder。

##### 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: Optional[TreeNode]) -> List[int]:
        stack, result = [], []
        node = root
        while True:
            while node is not None:
                result.append(node.val)
                stack.append(node)
                node = node.right
            if not stack:
                return reversed(result)
            node = stack.pop()
            node = node.left

##### 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: Optional[TreeNode]) -> List[int]:
        stack, result = [root], []
        while stack:
            node = stack.pop()
            if node is not None:
                result.append(node.val)
                stack.append(node.left)
                stack.append(node.right)
        
        return reversed(result)

Other methods:
- [Preorder, Inorder, and Postorder Iteratively Summarization](https://leetcode.com/problems/binary-tree-postorder-traversal/discuss/45551/Preorder-Inorder-and-Postorder-Iteratively-Summarization)
- [Share my two Python iterative solutions, post-order and modified preorder then reverse](https://leetcode.com/problems/binary-tree-postorder-traversal/discuss/45785/Share-my-two-Python-iterative-solutions-post-order-and-modified-preorder-then-reverse)

### 3. Morris Traversal
#### $O(n)$ runtime, $O(1)$ space

##### 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 reverse(self, start, end):
        if start is end:
            return
        
        n1, n2 = start, start.right
        while True:
            tmp = n2.right
            n2.right = n1
            n1 = n2
            n2 = tmp
            if n1 is end:
                break
    
    def printReverse(self, result, start, end):
        self.reverse(start, end)
        
        node = end
        while True:
            result.append(node.val)
            if node is start:
                break
            node = node.right
            
        self.reverse(end, start)
    
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        node = TreeNode(0, left=root)
        while node is not None:
            if node.left is None:
                node = node.right
            else:
                # Find the inorder predecessor of current node
                pred = node.left
                while pred.right is not None and pred.right is not node:
                    pred = pred.right
                
                # If the right child of inorder predecessor already points to
                # the current node, restore the original tree and update the 
                # current node to it's right child
                if pred.right is node:
                    self.printReverse(result, node.left, pred)
                    pred.right = None
                    node = node.right
                
                # Make current node as right child of its inorder predecessor
                else:
                    pred.right = node
                    node = node.left
        
        return result

Ref: https://www.796t.com/content/1545897069.html

###### tags: `leetcode`