# ####iteratively, use stacks
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res,stack,cur = [],[],root
        while stack or cur:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                res.append(cur.val)
                cur = cur.right
        return res
    
    ######recursively

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        self.inorderTraversalRecu(root, res)
        return res
        
    def inorderTraversalRecu(self, cur, res):
        if cur:
            self.inorderTraversalRecu(cur.left, res)
            res.append(cur.val)
            self.inorderTraversalRecu(cur.right, res)
            

63fb47d079a7f4b117942cd1e2d3cdf94a354910
<mask token>


class Solution(object):
    <mask token>

    def inorderTraversalRecu(self, cur, res):
        if cur:
            self.inorderTraversalRecu(cur.left, res)
            res.append(cur.val)
            self.inorderTraversalRecu(cur.right, res)

<mask token>


class Solution(object):

    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        self.inorderTraversalRecu(root, res)
        return res

    def inorderTraversalRecu(self, cur, res):
        if cur:
            self.inorderTraversalRecu(cur.left, res)
            res.append(cur.val)
            self.inorderTraversalRecu(cur.right, res)

class Solution(object):
    <mask token>


class Solution(object):

    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        self.inorderTraversalRecu(root, res)
        return res

    def inorderTraversalRecu(self, cur, res):
        if cur:
            self.inorderTraversalRecu(cur.left, res)
            res.append(cur.val)
            self.inorderTraversalRecu(cur.right, res)

class Solution(object):

    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res, stack, cur = [], [], root
        while stack or cur:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                res.append(cur.val)
                cur = cur.right
        return res


class Solution(object):

    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        self.inorderTraversalRecu(root, res)
        return res

    def inorderTraversalRecu(self, cur, res):
        if cur:
            self.inorderTraversalRecu(cur.left, res)
            res.append(cur.val)
            self.inorderTraversalRecu(cur.right, res)

# ####iteratively, use stacks
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res,stack,cur = [],[],root
        while stack or cur:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                res.append(cur.val)
                cur = cur.right
        return res
    
    ######recursively

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        self.inorderTraversalRecu(root, res)
        return res
        
    def inorderTraversalRecu(self, cur, res):
        if cur:
            self.inorderTraversalRecu(cur.left, res)
            res.append(cur.val)
            self.inorderTraversalRecu(cur.right, res)
            
