add a solution for 450

fishercoder1534 · fishercoder1534 · commit 90ed4fddf91f · 2021-10-28T13:21:17.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_450.java b/src/main/java/com/fishercoder/solutions/_450.java
@@ -2,9 +2,11 @@
 
 import com.fishercoder.common.classes.TreeNode;
 
+import java.util.ArrayList;
+import java.util.List;
+
 public class _450 {
     public static class Solution1 {
-
         /**
          * credit: https://discuss.leetcode.com/topic/65792/recursive-easy-to-understand-java-solution
          * Steps:
@@ -45,4 +47,101 @@ private TreeNode getMin(TreeNode node) {
         }
     }
 
+    public static class Solution2 {
+        /**
+         * My original, but brute force solution, time complexity: O(n) instead of O(h)
+         */
+        public TreeNode deleteNode(TreeNode root, int key) {
+            List<Integer> list = new ArrayList<>();
+            dfs(root, key, list);
+            return formBst(list, 0, list.size() - 1);
+        }
+
+        private TreeNode formBst(List<Integer> list, int left, int right) {
+            if (left > right) {
+                return null;
+            }
+            int mid = left + (right - left) / 2;
+            TreeNode root = new TreeNode(list.get(mid));
+            root.left = formBst(list, left, mid - 1);
+            root.right = formBst(list, mid + 1, right);
+            return root;
+        }
+
+        private List<Integer> dfs(TreeNode root, int key, List<Integer> list) {
+            if (root == null) {
+                return list;
+            }
+            dfs(root.left, key, list);
+            if (root.val != key) {
+                list.add(root.val);
+            }
+            dfs(root.right, key, list);
+            return list;
+        }
+    }
+
+    public static class Solution3 {
+        /**
+         * credit: https://leetcode.com/problems/delete-node-in-a-bst/solution/
+         *
+         * Again, using a pen and paper to visualize helps a lot.
+         * Putting a BST into an inorder traversal array helps a lot to understand:
+         *
+         * The successor of a node is always: go the right once, and then go to the left as many times as possible，
+         * because the successor is the next smallest element that is larger than the current one: so going to the right one time
+         * makes sure that we are finding the larger one, and then keeping going to the left makes sure that we'll find the smallest one.
+         *
+         * The predecessor of a node is always: go the left once, and then go the right as many times as possible,
+         * because the predecessor is the largest element that is smaller than the current one: so going to the left once makes it smaller than the current node,
+         * then keeping going to the right makes sure that we are getting the largest element.
+         */
+        public TreeNode deleteNode(TreeNode root, int key) {
+            if (root == null) {
+                return null;
+            }
+            if (root.val < key) {
+                //delete from the right subtree
+                root.right = deleteNode(root.right, key);
+            } else if (root.val > key) {
+                //delete from the left subtree
+                root.left = deleteNode(root.left, key);
+            } else {
+                //delete this current node, three cases:
+                if (root.left == null && root.right == null) {
+                    //case 1: if this is a leaf
+                    root = null;
+                } else if (root.right != null) {
+                    //case 2: has a right child, regardless whether it has left children or not,
+                    //this is because we want to traverse the tree only once, so we'll want to keep going down the tree
+                    root.val = findSuccessor(root);//we find the value of the successor and assign it to current root.val
+                    root.right = deleteNode(root.right, root.val);//and then we delete this successor's value in the right subtree as it's been moved up
+                } else if (root.left != null) {
+                    //case 3: this node is not a leaf and no right child, but has a left child
+                    //That means that its successor is somewhere upper in the tree but we don't want to go back.
+                    //Let's use the predecessor here which is somewhere lower in the left subtree.
+                    root.val = findPredecessor(root);
+                    root.left = deleteNode(root.left, root.val);
+                }
+            }
+            return root;
+        }
+
+        private int findPredecessor(TreeNode root) {
+            root = root.left;
+            while (root.right != null) {
+                root = root.right;
+            }
+            return root.val;
+        }
+
+        private int findSuccessor(TreeNode root) {
+            root = root.right;
+            while (root.left != null) {
+                root = root.left;
+            }
+            return root.val;
+        }
+    }
+
 }
diff --git a/src/test/java/com/fishercoder/_450Test.java b/src/test/java/com/fishercoder/_450Test.java
@@ -1,37 +1,43 @@
 package com.fishercoder;
 
 import com.fishercoder.common.classes.TreeNode;
+import com.fishercoder.common.utils.TreeUtils;
 import com.fishercoder.solutions._450;
 import org.junit.BeforeClass;
 import org.junit.Test;
 
+import java.util.Arrays;
+
 import static org.junit.Assert.assertEquals;
 
 public class _450Test {
     private static _450.Solution1 solution1;
+    private static _450.Solution2 solution2;
+    private static _450.Solution3 solution3;
     private static TreeNode expected;
     private static TreeNode root;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _450.Solution1();
+        solution2 = new _450.Solution2();
+        solution3 = new _450.Solution3();
     }
 
     @Test
     public void test1() {
-        root = new TreeNode(5);
-        root.left = new TreeNode(3);
-        root.left.left = new TreeNode(2);
-        root.left.right = new TreeNode(4);
-        root.right = new TreeNode(6);
-        root.right.right = new TreeNode(7);
-
-        expected = new TreeNode(5);
-        expected.left = new TreeNode(4);
-        expected.right = new TreeNode(6);
-        expected.left.left = new TreeNode(2);
-        expected.right.right = new TreeNode(7);
+        root = TreeUtils.constructBinaryTree(Arrays.asList(5, 3, 6, 2, 4, null, 7));
+        TreeUtils.printBinaryTree(root);
 
+        expected = TreeUtils.constructBinaryTree(Arrays.asList(5, 4, 6, 2, null, null, 7));
+        TreeUtils.printBinaryTree(expected);
         assertEquals(expected, solution1.deleteNode(root, 3));
+
+        expected = TreeUtils.constructBinaryTree(Arrays.asList(5, 2, 6, null, 4, null, 7));
+        TreeUtils.printBinaryTree(expected);
+        assertEquals(expected, solution2.deleteNode(root, 3));
+
+        expected = TreeUtils.constructBinaryTree(Arrays.asList(5, 4, 6, 2, null, null, 7));
+        assertEquals(expected, solution3.deleteNode(root, 3));
     }
 }
