[94] Binary Tree Inorder Traversal

https://leetcode.com/problems/binary-tree-inorder-traversal/description/

• algorithms
• Medium (53.38%)
• Source Code: 94.binary-tree-inorder-traversal.py
• Total Accepted: 439.3K
• Total Submissions: 784.8K
• Testcase Example: '[1,null,2,3]'

Given a binary tree, return the inorder traversal of its nodes' values.

Example:

Input: [1,null,2,3] 1
2 / 3

Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

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

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ret = []
        if not root: return ret

        self.inorder(root, ret)
        return ret

    def inorder(self, root, ret):
        if not root: return
        if root.left:
            self.inorder(root.left, ret)

        ret.append(root.val)

        if root.right:
            self.inorder(root.right, ret)