C# solution with explanation


  • 0
    K

    The key parts in this algorithm are:

    • It is possible to have the actual node to the leaf level to be the closest. So it is important to check till the very bottom, unless you find the exact match.
    • This means having to navigate through nodes that might not be optimal than the already found closest val.
    • The way to decide how or whether to navigate is based on node's val and the target
      • If node's val is less than the target and there's left node, go left.
      • If node's val is greater than the target and there's right node, go right.
    • A few good examples below:
      • [5,2,7,1,3,6,9,null, null, null, 4, null, null, 8, null], 8.37 -> Returns 8
      • [5,2,7,1,3,6,9,null, null, null, 4, null, null, 8, null], 8.67 -> Returns 9
      • [5,2,7,1,3,6,9,null, null, null, 4, null, null, 8, null], 4 -> Returns 4
    • Sample code below:
        public int ClosestValue(TreeNode root, double target) 
        {
            if (root != null)
            {
                return ClosestValueFromNode(root, target, root.val);
            }
            
            return 0;
        }
        
        private int ClosestValueFromNode(TreeNode node, double target, int closestValSoFar)
        {
            if (node == null || target == closestValSoFar)
            {
                return closestValSoFar;
            }
            
            var closestValDiff = Math.Abs(target - closestValSoFar);
            TreeNode nextNode = null;
            if (node.left != null && target < node.val)
            {
                if (Math.Abs(node.left.val - target) < closestValDiff)
                {
                    closestValSoFar = node.left.val;            
                }
                
                nextNode = node.left;
            }
            else if( node.right != null && target > node.val)
            {
                if (Math.Abs(node.right.val - target) < closestValDiff)
                {
                    closestValSoFar = node.right.val;
                }
                
                nextNode = node.right;
            }
            
            return ClosestValueFromNode(nextNode, target, closestValSoFar);               
        }
    

Log in to reply
 

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