`mid = low + (high -low)//2` 与 `(low + high)//2`

Question

我正在研究树问题Convert Sorted Array to Binary Search Tree - LeetCode

给定一个元素按升序排序的数组，将其转换为高度平衡的 BST。

对于这个问题，高度平衡二叉树被定义为一个二叉树，其中每个节点的两个子树的深度相差永远不会超过 1。

例子：

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0

     / \

   -3   9

   /   /

 -10  5

直观的 D&Q 解决方案是

class Solution:

    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:

        """

        Runtime: 64 ms, faster than 84.45%

        Memory Usage: 15.5 MB, less than 5.70% 

        """

        if len(nums) == 0: return None

        #if len(nums) == 1: return TreeNode(nums[0])

        mid = len(nums) // 2

        root = TreeNode(nums[mid])

        if len(nums) == 1: return root 

        if len(nums) > 1: 

            root.left = self.sortedArrayToBST(nums[:mid])

            root.right = self.sortedArrayToBST(nums[mid+1:])

        return root        

mid设置为len(nums)//2或(low + high)//2

当阅读其他提交时，我发现

class Solution:

    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:

        return self.buildBST(nums, 0, len(nums))

    def buildBST(self, nums, left, right):

        if right <= left:

            return None

        if right == left + 1:

            return TreeNode(nums[left])

        mid = left + (right - left) // 2

        root = TreeNode(nums[mid])

        root.left = self.buildBST(nums, left, mid)

        root.right = self.buildBST(nums, mid + 1, right)

        return root

mid 被设置为 mid = low + (high -low)//2

mid = low + (high -low)//2超过有(low + high)//2什么好处？

Answer 1

这是一种避免整数溢出的模式；该代码可能是从具有固定大小整数的语言移植而来的。当索引可以变得与用于包含它们的类型一样大时，中间low + high值的溢出就会成为一个问题，导致未定义的行为、错误的结果和漏洞。（这甚至会发生在大整数类型中，例如size_t当您搜索不是数组的内容时。）… 但在 Python 中，没有整数溢出，所以你是对的，你可以只做(low + high) // 2.

Answer 2

在许多语言中，例如 C++、JAVA。整数有固定的取值范围，例如：int32: -2147483648 ~ 2147483647int64: -9223372036854775808 ~ 9223372036854775807有时在有效范围内的低和高，但low + high可能会溢出。所以使用差异更安全&nbsp;mid = low + (high -low)//2但对于 python 来说不是必需的，因为它的工作方式类似于BigIntegerJava。