Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- /*
- Iterative Solution
- Time Complexity: O(N) - If the tree is skewed it will visit all nodes.
- Space Complexity: O(1)
- N = Total number of nodes in the BST
- */
- class Solution {
- public int closestValue(TreeNode root, double target) throws NullPointerException {
- if (root == null) {
- throw new NullPointerException("Input Tree root is null");
- }
- int closest = root.val;
- while (root != null) {
- if (Math.abs(root.val - target) < Math.abs(closest - target)) {
- closest = root.val;
- }
- if (target == root.val) {
- break;
- }
- root = target < root.val ? root.left : root.right;
- }
- return closest;
- }
- }
- /*
- Recursive Solution
- Time Complexity: O(N) - If the tree is skewed it will visit all nodes.
- Space Complexity: O(H)
- N = Total number of nodes in the BST
- H = Height of the binary Tree. (Recursion Stack)
- */
- class Solution {
- public int closestValue(TreeNode root, double target) throws NullPointerException {
- if (root == null) {
- throw new NullPointerException("Input Tree root is null");
- }
- int[] closest = new int[1];
- closest[0] = root.val;
- closestValueHelper(closest, root, target);
- return closest[0];
- }
- public void closestValueHelper(int[] closest, TreeNode node, double target) {
- if (node == null) {
- return;
- }
- if (target == node.val) {
- closest[0] = node.val;
- return;
- }
- if (Math.abs(node.val - target) < Math.abs(closest[0] - target)) {
- closest[0] = node.val;
- }
- if (target < node.val) {
- closestValueHelper(closest, node.left, target);
- } else {
- closestValueHelper(closest, node.right, target);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement