Week 2 homework submit

bcx20 · bcx20 · commit fe17840433c6 · 2020-06-21T04:20:28.000-04:00
diff --git a/Week02/BinaryTreeInorderTraversalIterative.java b/Week02/BinaryTreeInorderTraversalIterative.java
@@ -0,0 +1,26 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public List<Integer> inorderTraversal(TreeNode root) {
+        List<Integer> res = new ArrayList<Integer>();
+        Stack<TreeNode> stk = new Stack<TreeNode>();
+        TreeNode currentNode = root;
+        while(currentNode != null || !stk.empty()) {
+            while(currentNode != null) {
+                stk.push(currentNode);
+                currentNode = currentNode.left;
+            }
+            currentNode = stk.pop();
+            res.add(currentNode.val);
+            currentNode = currentNode.right;
+        }
+        return res;
+    }
+}
diff --git a/Week02/BinaryTreeInorderTraversalRecursive.java b/Week02/BinaryTreeInorderTraversalRecursive.java
@@ -0,0 +1,23 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public List<Integer> inorderTraversal(TreeNode root) {
+        List<Integer> res = new ArrayList<Integer>();
+        this.traverse(res, root);
+        return res;
+    }
+
+    public void traverse(List<Integer> res, TreeNode root) {
+        if (root == null) return;
+        this.traverse(res, root.left);
+        res.add(root.val);
+        traverse(res, root.right);
+    }
+}
diff --git a/Week02/BinaryTreePreorderTraversalIterative.java b/Week02/BinaryTreePreorderTraversalIterative.java
@@ -0,0 +1,26 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public List<Integer> preorderTraversal(TreeNode root) {
+        List<Integer> res = new ArrayList<Integer>();
+        Stack<TreeNode> stk = new Stack<TreeNode>();
+        TreeNode currentNode = root;
+        while(currentNode != null || !stk.empty()) {
+            while(currentNode != null) {
+                res.add(currentNode.val);
+                stk.push(currentNode);
+                currentNode = currentNode.left;
+            }
+            currentNode = stk.pop();
+            currentNode = currentNode.right;
+        }
+        return res;
+    }
+}
diff --git a/Week02/BinaryTreePreorderTraversalRecursive.java b/Week02/BinaryTreePreorderTraversalRecursive.java
@@ -0,0 +1,23 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public List<Integer> preorderTraversal(TreeNode root) {
+        List<Integer> res = new ArrayList<Integer>();
+        this.traverse(res, root);
+        return res;
+    }
+
+    public void traverse(List<Integer> res, TreeNode root) {
+        if(root == null) return;
+        res.add(root.val);
+        this.traverse(res, root.left);
+        this.traverse(res, root.right);
+    }
+}
