Given a binary tree, return the inorder traversal of its nodes' values.
YouTube
Input: [1, null, 2, 3]
1
\
2
/
3
Output: [1, 3, 2]
Last updated
Was this helpful?
Was this helpful?
// 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);
}
}
}/**
* Time complexity : O(n)
* Space complexity : O(n)
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> resultList = new ArrayList<>();
if(root == null) return resultList;
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while(curr != null || !stack.isEmpty()) {
while(curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
resultList.add(curr.val);
curr = curr.right;
}
return resultList;
}
}