最接近的二叉搜索树值

难度: Easy

Submission

运行时间: 23 ms

内存: 18.0 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
        def calDiff(root):
            if not root:
                return None

            diff = abs(root.val - target)
            nodeVal.append((root.val, diff))

            if target <= root.val:
                calDiff(root.left)
            elif target > root.val:
                calDiff(root.right)

        nodeVal = []
        calDiff(root)
        nodeVal.sort(key=lambda x:(x[1], x[0]))
        return nodeVal[0][0]

Explain

该题解的思路是使用递归的方式对二叉搜索树进行遍历。首先定义一个内部函数calDiff，用于计算当前节点值与目标值之间的差值的绝对值，并将节点值和差值作为元组存储在nodeVal列表中。然后根据目标值与当前节点值的大小关系，选择递归遍历左子树或右子树。最后对nodeVal列表按照差值和节点值进行排序，返回差值最小的节点值。

时间复杂度: O(nlogn)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
        def calDiff(root):
            if not root:
                return None

            # 计算当前节点值与目标值之间的差值的绝对值
            diff = abs(root.val - target)
            nodeVal.append((root.val, diff))

            # 根据目标值与当前节点值的大小关系，选择递归遍历左子树或右子树
            if target <= root.val:
                calDiff(root.left)
            elif target > root.val:
                calDiff(root.right)

        nodeVal = []
        calDiff(root)
        # 对nodeVal列表按照差值和节点值进行排序
        nodeVal.sort(key=lambda x:(x[1], x[0]))
        # 返回差值最小的节点值
        return nodeVal[0][0]

Explore

在递归函数`calDiff`中，当`root`为`None`时返回`None`是一种常见的递归终止条件，用于处理空树或者到达叶子节点的子节点。这种处理确保了递归能够在没有更多节点可遍历时正确结束。对于最终结果没有直接影响，因为我们收集的是非空节点的值和差值，而返回`None`只是表示停止在当前路径上的进一步遍历。

在递归调用结束后对`nodeVal`列表进行排序是出于简化代码逻辑和降低实现复杂度的考虑。虽然在插入时维护一个有序列表（例如使用优先队列）可以在某些情况下提高效率，但它可能需要更复杂的数据结构和额外的逻辑来确保正确性。在这种情况下，由于我们不知道会收集多少节点数据，统一在收集完后排序是一个简单且有效的策略。

使用差值作为主要排序关键字，并在差值相同的情况下选择最小的节点值，是一个合理的选择，特别是在没有其他优先级指示的情况下。这种方法确保了即使多个节点具有相同的差值，也能返回一个一致和可预测的结果。然而，这是否是最佳选择可能取决于具体的应用场景。在某些情况下，可能需要根据实际需要选择最大的节点值或其他属性。

是的，存在更优的方法利用二叉搜索树的性质来减少遍历的节点数。可以在遍历过程中维护一个当前最接近的值，只向可能包含更接近目标值的子树方向递归。例如，如果目标值小于当前节点值，只递归访问左子树；如果目标值大于当前节点值，只递归访问右子树。这种方法利用了二叉搜索树的有序性质，减少了不必要的遍历，从而提高了效率。