270. Closest Binary Search Tree Value

class Solution { public: int closestValue(TreeNode* root, double target) { if (root->val == target) return root->val; if (target < root->val){ // on the left side // 1) no left subtree if (!root->left) return root->val; TreeNode * ptr = root->left; // 2) yes, has a left subtree while(ptr->right != nullptr){ ptr = ptr->right; } if (abs((double)root->val - target) < abs((double)ptr->val - target)) return root->val; else return closestValue(root->left, target); } if (target > root->val){ // on the right side // 1) no right subtree if (!root->right) return root->val; TreeNode * ptr = root->right; // 2) yes, has a right subtree while(ptr->left != nullptr){ ptr = ptr->left; } if (abs((double)root->val - target) < abs((double)ptr->val - target)) return root->val; else return closestValue(root->right, target); } } };
Mistakes:
1) Note the function signature and return value. Spent hours debugging a wrong return type.
2) Note when to set the pointer. First set it to root->left, after that all the way right. Made a mistake in setting that to root itself and all the way right.

Be the first to comment

You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.