452. In-Order Walk
A museum organises its exhibits in a binary tree stored in root: the exhibits on the left of a hall come first, then the hall's own exhibit, then those on the right. The curator wants the guided-tour order.
Return the node values in in-order: for every node, all values of its left subtree appear first, then the node's own value, then all values of its right subtree. The result is an array with one entry per node. For an empty tree return an empty array.
Example 1
- Input:
- root = [6,2,9,1,4]
- Output:
- [1,2,4,6,9]
- Explanation:
Left subtree of 6 is 1-2-4 in order, then 6 itself, then 9.
Example 2
- Input:
- root = [3,null,8,5]
- Output:
- [3,5,8]
- Explanation:
3 has no left child, so it comes first; then the right subtree 8 has left child 5, giving 5 then 8.
Constraints
0 ≤ number of nodes ≤ 105
-1000 ≤ node value ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)