BT-inorder-traversal-stack

94. Binary Tree Inorder Traversal.py

# 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:
    """
    root->left->right(pre-order)
    left->right->root(post-order)
    left->root->right(in-order)
    
     1
    /  \
   2    3
   2->1->3
    """
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        inorder = []
        stack = [] # [1,2]
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            # 差別在這, 因為inorder left node first所以這裡要append
            inorder.append(root.val) 
            root = root.right
        return inorder
    
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        preorder = []
        stack = [] # [3]
        while root or stack:
            # while root 這個block: inorder和preorder長一樣
            while root:
                stack.append(root)
                preorder.append(root.val) # 差別在這, 因為pre-order root node first所以這裡要append
                root = root.left
            # after root之後的模塊: inorder也和preorder長一樣
            root = stack.pop() 
            root = root.right
        return preorder
    
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return None
        postorder = [] # [1,3,2]
        stack = [root] # [2,3]
        while stack:
            root = stack.pop()
            postorder.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)

        return postorder[::-1]