LeetCode 94 – Python 3 (Week 2 – 07)

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

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        
        inordertree = []
        #Recursive solution
        #Inorder traversal a tree: traverse the left subtree -> the root -> traverse the right subtree. 
        self.helper(root, inordertree)
        return inordertree
        
    
    def helper(self, root: TreeNode, res):
        if root is not None:
            self.helper(root.left, res)
            res.append(root.val)
            self.helper(root.right, res)

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

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        
        inordertree = []
        stack = []
        #Iterasive solution
        #Inorder traversal a tree: traverse the left subtree -> the root -> traverse the right subtree. The first value is the value of left leaf. Use a stack to store the nodes we traversed. This method is from bottom to top.
        
        while stack or root:
            if root:
                stack.append(root)
                root = root.left #in the last step, root is None
            ##when root is not trure, stack store the left leaf
            else:
                #store the left leaf
                node = stack.pop()
                inordertree.append(node.val) #store the root of left leaf.
                root = node.right

        return inordertree