0%

# Problem94

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

ps:preorder,inorder,postorder，前中后

# Key

## recursive approach

Solution

Runtime: 0 ms, faster than 100.00% of Java online submissions for Binary Tree Inorder Traversal.

Memory Usage: 37.9 MB, less than 5.11% of Java online submissions for Binary Tree Inorder Traversal.

Complexity Analysis

• Time complexity : O(n)O(n). The time complexity is O(n)O(n) because the recursive function is T(n) = 2 \cdot T(n/2)+1T(n)=2⋅T(n/2)+1.
• Space complexity : The worst case space required is O(n)O(n), and in the average case it’s O(\log n)O(logn) where nn is number of nodes.

## stack

solution还提供了另外一种方法通过stack pop的方式来完成：