[LeetCode Medium] BST - Delete Node in a BST !!

이건..무식하게 푼 것

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { TreeNode parent = null; int flag = -1; public TreeNode deleteNode(TreeNode root, int key) { TreeNode result = delete(root, key); return result; } private TreeNode delete(TreeNode root, int val) { if(root == null) return null; if(root.val > val) { // 왼쪽으로 parent = root; flag = 1; delete(root.left, val); } else if (root.val < val) { // 오른쪽으로 parent = root; flag = 0; delete(root.right, val); } else { // 삭제할 Node를 찾음 if(root.left == null && root.right == null) { // 1) 자식 Node 없음 if(flag == 0) parent.right = null; else if(flag == 1) parent.left = null; else root = null; return root; } else if (root.left != null && root.right == null) { // 2) 자식 Node 1개 (left) if(flag == 0) parent.right = root.left; else if(flag == 1) parent.left = root.left; else root = root.left; return root; } else if (root.right != null && root.left == null) { // 2) 자식 Node 1개 (right) if(flag == 0) parent.right = root.right; else if(flag == 1) parent.left = root.right; else root = root.right; return root; } else { // 3) 자식 Node 2개 TreeNode chgNode = findMin(root.right); int tmp = root.val; root.val = chgNode.val; chgNode.val = tmp; parent = root; flag = 0; delete(root.right, tmp); return root; } } return root; } private TreeNode findMin(TreeNode node) { while(node.left != null) { node = node.left; } return node; } }

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode deleteNode(TreeNode root, int key) { if(root == null) return null; if(key < root.val){ root.left = deleteNode(root.left, key); }else if(key > root.val){ root.right = deleteNode(root.right, key); }else{ if(root.left == null){ return root.right; }else if(root.right == null){ return root.left; }else{ int minVal = findMin(root.right); root.val = minVal; root.right = deleteNode(root.right, minVal); } } return root; } private int findMin(TreeNode root){ while(root.left != null){ root = root.left; } return root.val; } }