270. Closest Binary Search Tree Value

三刷 05/2022

Version #1 Iteration 

Time O(h)

Space O(1)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Closest Binary Search Tree Value.

Memory Usage: 43.6 MB, less than 51.53% of Java online submissions for Closest Binary Search Tree Value.

/**

 * 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) {

        if (root == null) {

            throw new IllegalArgumentException("given root cannot be empty");

        }

        // Search for the target value from root to leaf

        // Update the minimum difference along the path

        double diff = Double.MAX_VALUE;

        int result = 0;

        TreeNode curr = root;

        while (curr != null) {

            if (curr.val == target) {

                return curr.val;

            }

            double currDiff = Math.abs(curr.val - target);

            if (currDiff < diff) {

                diff = currDiff;

                result = curr.val;

            }

            if (curr.val > target) {

                curr = curr.left;

            } else {

                curr = curr.right;

            }

        }

        return result;

    }

}

二刷
下面一刷时候用的iteration 感觉更好
Recursion  O(h)
100.00 %
class Solution {
    public int closestValue(TreeNode root, double target) {
        int[] result = new int[1];
        if (root != null) {
            result[0] = root.val;
            helper(root, target, result);
        }
        return result[0];
    }
    private void helper(TreeNode node, double target, int[] result) {
        if (node == null) {
            return;
        }
        if (Math.abs(node.val - target) < Math.abs(result[0] - target)) {
            result[0] = node.val;
        }
        // if node.val == target, just return
        if (node.val > target) {
            helper(node.left, target, result);
        }
        if (node.val < target) {
            helper(node.right, target, result);
        }
    }
}

一刷
做完以后发现非常慢，大概只beats 2%
发现题意里面没有相等的情况，去掉判断相等而提前返回这部分
75.10%
如果自己定义method的的话，要写成
public int closestValue(TreeNode root, double target) throws Exception {
...
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int closestValue(TreeNode root, double target) {
        if (root == null) throw new IllegalArgumentException();
        TreeNode curr = root;
        int result = curr.val;
        while (curr != null) {
            //if (curr.val == target) return curr.val;
         
            if (Math.abs(curr.val - target) < Math.abs(result - target)) result = curr.val;
         
            if (curr.val > target) {
                curr = curr.left;
            } else {
                curr = curr.right;
            }
        }
        return result;
    }
}