Binary Tree Inorder Traversal
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]
Explanation:
Example 2:
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,2,6,5,7,1,3,9,8]
Explanation:
Example 3:
Input: root = []
Output: []
Example 4:
Input: root = [1]
Output: [1]
Constraints:
The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100
My Solution
We complete the inorder traversal by recursively visiting the left node, then adding the current node to the list, and finally traversing the right node. Since we visit all the nodes once, time complexity would be O(n). Space complexity would be O(1) since we just require constant extra space.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> out = new ArrayList<>();
List<Integer> left = new ArrayList<>();
List<Integer> right = new ArrayList<>();
if (root == null) {
return out;
}
if (root.left != null) {
left = inorderTraversal(root.left);
}
for (int i = 0; i < left.size(); i++) {
out.add(left.get(i));
}
out.add(root.val);
if (root.right != null) {
right = inorderTraversal(root.right);
}
for (int i = 0; i < right.size(); i++) {
out.add(right.get(i));
}
return out;
}
}