leetcode 94 Binary Tree Inorder Traversal
z
 2018-08-19 16:26:06  

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 Solution{
    	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 Solution {
        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;
        }
    }