class Test(): def heap_sort(self, nums): i, l = 0, len(nums) self.nums = nums # 构造大顶堆，从非叶子节点开始倒序遍历，因此是l//2 -1 就是最后一个非叶子节点 for i in range(l//2-1, -1, -1): self.build_heap(i, l-1) print(nums) # 上面的循环完成了大顶堆的构造，那么就开始把根节点跟末尾节点交换，然后重新调整大顶堆 for j in range(l-1, -1, -1): nums, nums[j] = nums[j], nums self.build_heap(0, j-1) return nums def build_heap(self, i, l): """构建大顶堆""" nums = self.nums left, right = 2*i+1, 2*i+2 ## 左右子节点的下标 large_index = i if left <= l and nums[i] < nums[left]: large_index = left if right <= l and nums[left] < nums[right]: large_index = right # 通过上面跟左右节点比较后，得出三个元素之间较大的下标，如果较大下表不是父节点的下标，说明交换后需要重新调整大顶堆 if large_index != i: nums[i], nums[large_index] = nums[large_index], nums[i] self.build_heap(large_index, l)
For this problem, a height-balanced binary tree is defined as:
a binary tree in which the left and right subtrees of every node differ in height by no more than 1.
This problem is an easy-level at Leetcode. I probably did it more than five times, once and once again. Just like a muscle memory.
However, I found an interesting solution today, which literally changed my mind about Python…
Here is the code:
# 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 isBalanced(self, root: TreeNode, h = 1) -> bool: if not root: return h l = self.isBalanced(root.left, h + 1) r = self.isBalanced(root.right, h + 1) return abs(l - r) <= 1 and max(l, r)
I am very confused at the last line, the max(l, r) part.
I thought that max(l, r) should be converted as a bool value even it returns a integer type value, because as the second component of the operation AND, max(l, r) should represent as a bool variable.
Following by my worst idea, I supposed that the function isBalanced would return either 1 (True) or 0 (False). However, I found a crazy truth after experiments, that Python executor actually return a integer value (the maximum value of l and r) if abs(l – r) <= 1 is matched.
So, it really makes sense. Gain new knowledge of Python 🙂
There are two methods to calculate the median of an interval [low, high].
l + h may have addition overflow, but h-l will not. Therefore, it is best to use the second method of calculation.