LeetCode#94: Binary Tree Inorder Traversal
First check out the problem description here on LeetCode.
The Solution
This is marked as a medium difficult problem. However if you know what in-order traversal does, it is a very simple problem. Here I just added a helper traverse()
method.
All the trick is done in the few lines inside the function. It checks if the current node is null, then it skips. Else it runs the same method recursively on the left child first, then it actually adds the current node’s value to the list called result
. Then it proceeds to the right child just like left one.
<pre class="wp-block-syntaxhighlighter-code">class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
return traverse(root, new ArrayList<Integer>());
}
private List<Integer> traverse(TreeNode node, List<Integer> result){
if (node==null) return result;
traverse(node.left, result);
result.add(node.val);
traverse(node.right, result);
return result;
}
}
Result
This solution beats 100% of the previous solutions by runtime and 99.62% by memory! Wooho!