Today I Learned

오늘 할일
1. LeetCode

• 450. Delete Node in a BST는 이진트리의 노드를 삭제하는 문제이다.
       이전의 코드는 말단노드를 삭제하지 못한다는 단점이 있어 DFS를 사용하여 해결해보았다.

/**
 * 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 {
    private TreeNode parent=null;
    private void DFS(TreeNode node, int key, TreeNode prev){
        if(node==null || parent!=null)
            return;

        if(node.val==key)
            parent=prev;
        
        if(node.left!=null)
            DFS(node.left, key, node);
        if(node.right!=null)
            DFS(node.right, key, node);
    }

    private void shift_copy(TreeNode node, TreeNode prev){
        System.out.printf("node: %d, prev: %d\n", node.val, prev.val);
        if(node.right!=null){
            node.val=node.right.val;
            shift_copy(node.right, node);
        } else{
            prev.right=null;
        }
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null)
            return null;
        if(root.val==key && root.left==null && root.right==null)
            return null;
        Queue<TreeNode> queue=new LinkedList();
        queue.add(root);
        int depth=0, count=1;
        while(!queue.isEmpty()){
            TreeNode node=queue.remove();
            
            if(node.val==key){
                if(node.left==null && node.right==null){
                    DFS(root, key, root);
                    if(parent.left==node)
                        parent.left=null;
                    if(parent.right==node)
                        parent.right=null;
                } else
                    shift_copy(node, node);
            }
            if(node.left!=null)
                queue.add(node.left);
            if(node.right!=null)
                queue.add(node.right);
        }
        return root;
    }
}

하지만 예상치 못한 케이스에서 fail이 발생했는데, 정렬된 트리상태여야 한다는 점을 이제야 얄게되었다. 그 전 까지는 우측 right값을 shift해서 가져오는 형태로 인지했었다.