binary tree inorder traversal

fishercoder1534 · fishercoder1534 · commit fc4c9be300cc · 2016-08-23T07:54:32.000-07:00
diff --git a/MEDIUM/src/medium/BinaryTreeInorderTraversal.java b/MEDIUM/src/medium/BinaryTreeInorderTraversal.java
@@ -0,0 +1,40 @@
+package medium;
+
+import java.util.List;
+import java.util.ArrayList;
+import java.util.Stack;
+
+import classes.TreeNode;
+
+public class BinaryTreeInorderTraversal {
+
+    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;
+    }
+
+
+}
