Easy

Binary Tree Inorder Traversal

014

Given a binary tree encoded as a level-order array with -100000 as null, return its inorder traversal.

EXAMPLES

Example 1

Input
{
  "root": [
    1,
    -100000,
    2,
    3
  ]
}

Output
[
  1,
  3,
  2
]

FUNCTION SHAPE

root: intArray→intArray

SOLUTION NOTE

h is the height of the tree. Similarly, see preorder (Q144) and postorder (Q145) traversals.

Reveal reference solution +

pythonREFERENCE

def inorderTraversal(self, root: TreeNode) -> List[int]:
    result = []

    def dfs(node):
        if not node:
            return
        dfs(node.left)         # Process left
        result.append(node.val)  # Process root
        dfs(node.right)        # Process right

    dfs(root)
    return result

TimeO(n)

SpaceO(h)

Open on LeetCode ↗