class Solution {
public:
int largestSmaller(TreeNode* root, int target) {
// write your solution here
if (!root) return INT_MIN;
if (root->value == target){
if (!root->left)
return INT_MIN;
else {
TreeNode * ptr = root->left;
while(ptr->right)
ptr = ptr->right;
return ptr->value;
}
}
else if (root->value > target){
return largestSmaller(root->left, target);
}
else {
// root->value < target
if (!root->right)
return root->value;
else {
TreeNode * ptr = root->right;
while(ptr->left)
ptr = ptr->left;
if (ptr->value >= target)
return root->value;
else return largestSmaller(root->right, target);
}
}
}
};
1. Note when root->val == target, cannot return the root of left subtree. Instead should return the largest number in the left subtree... thus should traverse to the rightmost end.
2. Note when ptr->vau == target the case, should also return root. i.e. in the last if condition.
2. Note when ptr->vau == target the case, should also return root. i.e. in the last if condition.
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.