package com.fishercoder.solutions;


import com.fishercoder.common.classes.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 94. Binary Tree Inorder Traversal
 *
 * Given a binary tree, return the inorder traversal of its nodes' values.

 For example:
 Given binary tree [1,null,2,3],
 1
  \
   2
  /
 3
 return [1,3,2].

 Note: Recursive solution is trivial, could you do it iteratively?*/

public class _94 {

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList();
        return inorder(root, result);
    }

    List<Integer> inorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return result;
        }
        if (root.left != null) {
            inorder(root.left, result);
        }
        result.add(root.val);
        if (root.right != null) {
            inorder(root.right, result);
        }
        return result;
    }

    public List<Integer> inorderTraversal_iterative(TreeNode root) {
        List<Integer> result = new ArrayList();
        Stack<TreeNode> stack = new Stack();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            result.add(root.val);
            root = root.right;
        }
        return result;
    }

}

@@ -29,17 +29,16 @@
 tions;%0A%0A
-%0A
 import c
@@ -448,16 +448,56 @@
  _94 %7B%0A%0A
+    public static class Solution1 %7B%0A    
     publ
@@ -555,52 +555,8 @@
     
-    List%3CInteger%3E result = new ArrayList();%0A
     
@@ -584,24 +584,41 @@
 ot, 
-result);%0A
+new ArrayList());%0A   
     
+ 
 %7D%0A%0A
+    
     
@@ -678,32 +678,36 @@
 sult) %7B%0A        
+    
 if (root == null
@@ -714,32 +714,36 @@
 ) %7B%0A            
+ 
+   
 return result;%0A 
@@ -752,43 +752,14 @@
     
- %7D%0A
      
-   if (root.left != null) %7B
+%7D
 %0A   
@@ -791,38 +791,32 @@
 t, result);%0A    
-    %7D%0A
         result.a
@@ -841,45 +841,18 @@
     
-if (root.right != null) %7B%0A           
+    return
  ino
@@ -895,34 +895,80 @@
     
+%7D%0A%0A
     
-return result;%0A    %7D%0A%0A
+public static class Solution2 %7B%0A        //iterative approach%0A    
     
@@ -1008,18 +1008,8 @@
 rsal
-_iterative
 (Tre
@@ -1014,32 +1014,36 @@
 reeNode root) %7B%0A
+    
         List%3CInt
@@ -1082,16 +1082,20 @@
         
+   
+ 
 Stack%3CTr
@@ -1119,24 +1119,28 @@
 ew Stack();%0A
+    
         whil
@@ -1182,32 +1182,36 @@
 ) %7B%0A            
+    
 while (root != n
@@ -1233,16 +1233,20 @@
         
+ 
+   
 stack.pu
@@ -1251,24 +1251,28 @@
 push(root);%0A
+    
             
@@ -1297,34 +1297,42 @@
 ft;%0A            
+   
+ 
 %7D%0A
+    
             root
@@ -1351,32 +1351,36 @@
 ();%0A            
+    
 result.add(root.
@@ -1389,32 +1389,36 @@
 l);%0A            
+ 
+   
 root = root.righ
@@ -1428,26 +1428,33 @@
         
-%7D%0A
+    %7D%0A   
         
 return r
@@ -1437,32 +1437,33 @@
    %7D%0A           
+ 
 return result;%0A 
@@ -1465,13 +1465,22 @@
 lt;%0A    
+    %7D%0A    
 %7D
-%0A
 %0A%7D%0A

refactor 94