menu

[LeetCode] 094. Binary Tree Inorder Traversal *

Problem (Medium)

094. Binary Tree Inorder Traversal

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?

Tree Traversals (Inorder, Preorder and Postorder)

Depth First Traversals: (a) Inorder (Left, Root, Right) : 4 2 5 1 3 (b) Preorder (Root, Left, Right) : 1 2 4 5 3 (c) Postorder (Left, Right, Root) : 4 5 2 3 1

Approach 1: Recursive *

Idea

The first method to solve this problem is using recursion. This is the classical method and is straightforward. We can define a helper function to implement recursion.

Solution

Complexity

  • Time: $O(n)$
  • Space: $O(n)$

Approach 2: Iterating method using Stack *

Idea

The strategy is very similiar to the first method, the different is using stack.

Solution

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

Complexity

  • Time: $O(n)$
  • Space: $O(n)$



KF

Comments