Java - Simple & Easy to understand solution using recursion


  • 0
    T
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        double min = Double.MAX_VALUE;
        double minDiff = Double.MAX_VALUE;
        public int closestValue(TreeNode root, double target) {
            
            if(root==null) return 0;
            
            int val = root.val;
            if(val == (int)target) return val;
            
            helper(root,target);
            return (int)min;
        }
        
        private void helper(TreeNode root, double target){
            if(root == null) return ;
            int val = root.val;
            double diff = Math.abs( target - (double)val );
            minDiff = Math.min(minDiff, diff );
            if(minDiff==diff){
                min = root.val;
            }
            if(root.val > target){ // if root value > target, then go left, if left doesn't exist then root itself would be closest to target, all nodes to the right of root would be greater than root & hence the difference would go on increasing from here.
                if(root.left!=null) helper(root.left,target);
                else return ;
            }else{ // similar explanation as above. If root.val < target then go right, if you go left, then the difference would be more than difference between target and root.val . So there is no point in going to the left hence return;
                if(root.right!=null) helper(root.right, target);
                else return;
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.