Leetcode 270) Closest Binary Search Tree Value

17 Sep 2021 in Algorithms

My solution

• 바이너리 새풀이

/**
 * 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 {
    double min=Double.MAX_VALUE;
    int res=0;
    public int closestValue(TreeNode root, double target) {
        if(root==null){
            return res;
        }

        if(min>Math.abs(root.val-target)){
            res=root.val;
            min=Math.abs(root.val-target);
        }

        if(root.val>=target){
            return closestValue(root.left,target);
        }else{
            return closestValue(root.right,target);

        }

    }
}

Other Answer

• 엄청 깔쌈하게 풀엇넹..

/**
 * 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 int closestValue(TreeNode root, double target) {
        int ret = root.val;   
        while(root != null){
            if(Math.abs(target - root.val) < Math.abs(target - ret)){
                ret = root.val;
            }      
            root = root.val > target? root.left: root.right;
        }     
        return ret;
    }
}

오답

• 아니.. 트리는 null이 있을 수 있다는 사실을 잠깐 망각하고 있었다.

  1. if문 구조를 ㅈ같이 짬
  2. tmp = root.left해서 업데이트가 죽어도 안되게 해놓음.. 븅신인가.. tmp=tmp.left란다~

• 테스트 케이스 이거일 때 오류났다.

  [1,null,2]
  3.428571
  

• 전체 코드

/**
 * 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 int closestValue(TreeNode root, double target) {
        TreeNode tmp = root;
        while(tmp.left!=null || tmp.right!=null){
            double left = tmp.val;
            double right = tmp.val;
            double current = Math.abs(tmp.val-target);
            if(tmp.left!=null){
                left = Math.abs(target-tmp.left.val);
            }
            if(tmp.right!=null){
                right = Math.abs(target-tmp.right.val);
            }
            if(current <left && current <right){
                return tmp.val;
            }else if(current>left){
                tmp=root.left;
            }else if(current<right){
                //아 글구 여기 부등호 방향 잘못됨. CURRENT>RIGHT이어야한다.
                //아.. 븅신인가root.right가 아니라tmp right이네
                tmp=root.right;
            }
        }
        return tmp.val;
    }
}

오답 2 - 오답은 아닌데, binary search tree 가 무색하게 무식하게 풀음.

• 아래는 모든 노드를 탐색한, 이진탐색트리를 만들 필요도 없는 개꾸진 답안.

/**
 * 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 {
    Double closest;
    int val ;

    public int closestValue(TreeNode root, double target) {
        closest = Double.MAX_VALUE;
        //root가 null일수없다. 조건에서 null없음
        val=0;
        dfs(root,target);

        return val;
    }

    public void dfs(TreeNode tmp,Double target){
        double examine= Math.abs(tmp.val-target);
        if(examine<closest){
            closest=examine;
            val = tmp.val; 
        }
        if(tmp.left!=null){
            dfs(tmp.left,target);
        }
        if(tmp.right!=null){
            dfs(tmp.right,target);
        }

    }
}