add a solution for 285

fishercoder1534 · fishercoder1534 · commit 46348249ecb5 · 2021-04-08T07:26:18.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_285.java b/src/main/java/com/fishercoder/solutions/_285.java
@@ -2,7 +2,9 @@
 
 import com.fishercoder.common.classes.TreeNode;
 
+import java.util.ArrayList;
 import java.util.Iterator;
+import java.util.List;
 import java.util.Map;
 import java.util.TreeMap;
 
@@ -17,7 +19,7 @@ public static class Solution1 {
          * <p>
          * The time complexity should be O(h) where h is the depth of the result node.
          * succ is a pointer that keeps the possible successor.
-         * Whenever you go left the current root is the new possible successor, otherwise the it remains the same.
+         * Whenever you go left the current root is the new possible successor, otherwise it remains the same.
          * <p>
          * Only in a balanced BST O(h) = O(log n). In the worst case h can be as large as n.
          */
@@ -64,4 +66,31 @@ private void inorderTraversal(TreeNode root, TreeMap<Integer, TreeNode> map) {
         }
     }
 
+    public static class Solution3 {
+        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
+            List<TreeNode> inorder = new ArrayList<>();
+            dfs(root, inorder);
+            for (int i = 0; i < inorder.size() - 1; i++) {
+                if (inorder.get(i) == p) {
+                    return inorder.get(i + 1);
+                }
+            }
+            return null;
+        }
+
+        private List<TreeNode> dfs(TreeNode root, List<TreeNode> inorder) {
+            if (root == null) {
+                return inorder;
+            }
+            if (root.left != null) {
+                dfs(root.left, inorder);
+            }
+            inorder.add(root);
+            if (root.right != null) {
+                dfs(root.right, inorder);
+            }
+            return inorder;
+        }
+    }
+
 }
