Given a binary tree, return the inorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3}
,
1 \ 2 / 3
return [1,3,2]
.
1. Recursive Version
public ArrayList<Integer> inorderTraversal(TreeNode root) { //recursive version ArrayList<Integer> result = new ArrayList<>(); traversalHelper(root, result); return result; } public void traversalHelper(TreeNode root, ArrayList<Integer> result) { if (root == null) { return; } traversalHelper(root.left, result); result.add(root.val); traversalHelper(root.right, result); }
2. Non-recursive Version
public ArrayList<Integer> inorderTraversal(TreeNode root) { //non-recursive version ArrayList<Integer> result = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); TreeNode curr = root; while (curr != null || !stack.empty()) { TreeNode left = curr; while (left != null) { stack.push(left); left = left.left; } curr = stack.pop(); result.add(curr.val); curr = curr.right; } return result; }