lintcode 900 二叉搜索树中最接近的值

给一棵非空二叉搜索树以及一个target值,找到在BST中最接近给定值的节点值
样例1
输入: root = {5,4,9,2,#,8,10} and target = 6.124780
输出: 5
样例2
输入: root = {3,2,4,1} and target = 4.142857
输出: 4
注意事项
给出的目标值为浮点数
我们可以保证只有唯一一个最接近给定值的节点
//如果当前节点值小于目标值,则结果只可能是当前节点值或者右子树中的值;
//如果当前节点值大于目标值,则结果只可能是当前节点值或者左子树中的值

    TreeNode *findnearest(TreeNode *root,double target)
    {
        if( root == NULL || double(root->val) == target)
        {
            return root;
        }
        if( root->val > target)
        {
            if( !root->left )
            {
                return root;
            }else{
                TreeNode *node = findnearest(root->left,target);
                return fabs(node->val - target) > fabs(root->val - target) ? root:node;
            }
        }else{
            if( !root->right )
            {
                return root;
            }else{
                TreeNode *node = findnearest(root->right,target);
                return fabs(node->val - target) > fabs(root->val - target) ? root : node;
            }
        }
    }
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。