[LeetCode 75/Binary Search Tree] 700 - Search in a Binary Search Tree / 450 - Delete Node in a BST (Java)

700 - Search in a Binary Search Tree

---

풀이

BST에서 값이 val과 같은 노드 찾고 그 노드를 root로 하는 subtree

BST: 왼쪽 subtree < 현재 노드 < 오른쪽 subtree

• node.val > val -> 왼쪽으로 이동
• node.val < val -> 오른쪽으로 이동

---

코드

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) return null;

        if (root.val == val) return root;

        if (val < root.val) return searchBST(root.left, val);
        else return searchBST(root.right, val);
    }
}

---

450 - Delete Node in a BST

---

풀이

BST에서 값 key 가진 노드 찾아 삭제하고 삭제 후에도 BST 성질 유지

 

BST: 왼쪽 subtree < 현재 노드 < 오른쪽 subtree

• node.val > val -> 왼쪽으로 이동
• node.val < val -> 오른쪽으로 이동

 

삭제 3가지 경우

• 자식 X (leaf) -> `return null`
• 자식 하나 -> `return node.left` or `return node.right`
• 자식 둘 -> 오른쪽 subtree에서 가장 작은 값 or 왼쪽 subtree에서 가장 작은 값으로 대체

// case 1,2: 자식 0개 또는 1개
if (root.left == null) return root.right;
if (root.right == null) return root.left;

// case 3: 자식 2개
TreeNode min = findMin(root.right);
root.val = min.val;
root.right = deleteNode(root.right, min.val);

---

코드

class Solution {
    TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }

        return node;
    }

    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;
            if (root.right == null) return root.left;

            TreeNode min = findMin(root.right);
            root.val = min.val;
            root.right = deleteNode(root.right, min.val);
        }

        return root;
    }
}

---

출처

LeetCode 75 - Study Plan - LeetCode