Given a binary tree, return the inorder traversal of its nodes' values.
Constraints
Approach
Links
YouTube
Examples
Input: [1, null, 2, 3]
1
\
2
/
3
Output: [1, 3, 2]
Solutions
// 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;
}
}
/**
* Time complexity : O(n). The time complexity is O(n) because the recursive
* function is T(n) = 2 * T(n/2) + 1.
* Space complexity : The worst case space required is O(n), and in the average
* case it's O(logn) where nn is number of nodes.
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> resultList = new ArrayList<>();
inorder(root, resultList);
return resultList;
}
private void inorder(TreeNode root, List<Integer> resultList) {
if(root == null) return;
if(root.left != null) {
inorder(root.left, resultList);
}
resultList.add(root.val);
if(root.right != null) {
inorder(root.right, resultList);
}
}
}