LintCode/closestBinarySearchTreeValue/closestValue.cpp at master · WindZQ/LintCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <math>

#defind method1 1
#defind method2 0
#defind method3 0

class TreeNode
{
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int val)
    {
        this->val = val;
        this->left = this->right = NULL;
    }
};

class Solution
{
public:
#if method1
    int closestValue(TreeNode *root, double target)
    {
        int closest = root->val;

        while(root)
        {
            if(std::abs(closest - target) >= std::abs(root->val - target))
            {
                closest = root->val;
            }

            root = target < root->val ? root->left : root->right;
        }

        return closest;
    }
#endif

#if method2
    int closestValue(TreeNode *root, double target)
    {
        if(root == NULL) return -1;

        TreeNode *less_node = root;
        TreeNode *bigger_node = root;
        TreeNode *curt = root;

        while(curt != NULL)
        {
            if(curt->val == target)
            {
                return target;
            }
            else if(curt->val > target)
            {
                bigger_node = curt;
                curt = curt->left;
            }
            else
            {
                less_node = curt;
                curt = curt->right;
            }
        }

        if(std::abs(less_node->val - target) < std::abs(bigger_node->val - target))
        {
            return less_node->val;
        }

        return bigger_node->val;
    }
#endif

#if method3
    int closestValue(TreeNode *root, double target)
    {
        TreeNode *min = nullptr;
        double min_diff = std::numeric_limits<double>::max();

        while(root != nullptr)
        {
            double diff = std::abs(root->val - target);
            if(diff < min_diff)
            {
                min_diff = diff;
                min = root;
            }

            if(root->val == target) break;
            if(target < root->val)
            {
                root = root->left;
            }
            else
            {
                root = root->right;
            }
        }

        return (min == nullptr) ? 0 : min->val;
    }
#endif
};