Given the root of a binary tree, return the inorder traversal of its nodes’ values.
Example 1:
Input: root = [1,null,2,3] Output: [1,3,2]
Example 2:
Input: root = [] Output: []
Example 3:
Input: root = [1] Output: [1]
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Follow up: Recursive solution is trivial, could you do it iteratively?
Solution
When we try to understand the problem, it is basically asking for in order traversal of binary tree. I have actually studies all kinds of traversals. So it was actually easy for me this time. If you study the traversals once, you will be able to solve any kind of traversal problems using recursion.
The approach would be to do in order traversal of left element. Then do it for middle element. And then do it for the right element. Use an array to store these. Below is the java code.
class Solution {
private List<Integer> path = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return path;
}
inorderTraversal(root.left);
path.add(root.val);
inorderTraversal(root.right);
return path;
}
}And below is the efficiency. So it is the fastest solution ever submitted on LeetCode for this problem. 🙂
Things to keep in mind. Since it is recursion, you need to define the arraylist outside the loop. Think of what to return when the root is null.
