leetcode 94 binary tree inorder traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

Example:

1
2
3
4
5
6
7
8

Input: [1,null,2,3]
   1
    
     2
    /
   3

Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

• Recursive solution:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

  class { public static List<Integer> inorderTraversalRecursive(TreeNode root) { List<Integer> ans = new LinkedList<>(); helper(ans, root); return ans; } public static void helper(List<Integer> ans, TreeNode root) { if (root != null){ helper(ans, root.left); ans.add(root.val); helper(ans, root.right); } } }

• Iteritive solution

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

  class { public List<Integer> inorderTraversal(TreeNode root){ Stack<TreeNode> s = new Stack<>(); List<Integer> ans = new LinkedList<>(); while(!s.isEmpty() || root != null){ while(root != null){ s.add(root); root = root.left; } root = s.pop(); ans.add(root.val); root = root.right; } return ans; } }