题目描述

给一棵非空二叉搜索树以及一个target值，找到在BST中最接近给定值的节点值。

给出的目标值为浮点数

可以保证只有唯一一个最接近给定值的节点

测试样例

输入: root = {5,4,9,2,#,8,10} and target = 6.124780

输出: 5

解释：

二叉树 {5,4,9,2,#,8,10}，表示如下的树结构：

        5

      / \

    4    9

    /    / \

  2    8  10

输入: root = {3,2,4,1} and target = 4.142857

输出: 4

解释：

二叉树 {3,2,4,1}，表示如下的树结构：

    3

    / \

  2    4

/

1

解题思路与方法

1、BFS暴力解法

使用BFS将整棵树遍历一遍，在遍历过程中计算每个节点与目标的差值绝对值，并记录下它们的对应关系（可以使用一个dict来记录）。BFS完事后，将记录的最小差值绝对值对应的节点值返回即可。

2、分冶

i). 从根节点开始遍历，每次比较当前节点与目标的大小，若目标值小于当前节点值，则将当前节点当作“上限”，同时将当前节点更新为其左儿子；否则，将当前节点当作“下限”，同时将当前节点更新为其右儿子；

ii). 不断重复i)直至当前节点为空；

iii). 循环结束后，将得到的“上限”与“下限”分别与目标计算差值，若“上限”与目标的差值绝对值较小，则返回这个“上限”对应的值；否则返回“下限”对应的值

代码

1、BFS

from collections import deque

"""

Definition of TreeNode:

class TreeNode:

    def __init__(self, val):

        self.val = val

        self.left, self.right = None, None

"""

class Solution:

    """

    @param root: the given BST

    @param target: the given target

    @return: the value in the BST that is closest to the target

    """

    def closestValue(self, root, target):

        if not (root.left and root.right) or target == root:

            return root.val

        # 记录每个节点元素与target的接近程度，即它们差值的绝对值

        delta = {}

        q = deque([root])

        # BFS

        while q:

            node = q.popleft()

            v = node.val

            k = abs(node.val - target)

            # key为差值，value为树节点的值

            delta[k] = v

            if node.left:

                q.append(node.left)

            if node.right:

                q.append(node.right)

        # 按接近程度排序

        sorted_delta = sorted(delta.items(), key=lambda kv: kv[0])

        return sorted_delta[0][1]

2、分冶

"""

Definition of TreeNode:

class TreeNode:

    def __init__(self, val):

        self.val = val

        self.left, self.right = None, None

"""

class Solution:

    """

    @param root: the given BST

    @param target: the given target

    @return: the value in the BST that is closest to the target

    """

    def closestValue(self, root, target):

        if not (root.left and root.right) or target == root:

            return root.val

        # 下限

        lower = root

        # 上限

        upper = root

        # 当前节点

        current = root

        while current:

            # 目标值小于当前节点

            if target < current.val:

                # 将当前节点当作上限

                upper = current

                # 同时将当前节点更新为其左二子

                current = current.left

            # 目标值大于当前节点

            else:

                # 将当前节点当作下限

                lower = current

                # 同时将当前节点更新为其右儿子

                current = current.right

        lower_win = abs(target - lower.val) < abs(target - upper.val)

        return lower.val if lower_win else upper.val