Monthly Archives: June 2020

Heap sort

Posted on by
Reply 
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[0], nums[j] = nums[j], nums[0]
            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)

Is a Balanced Binary Tree

Posted on by
Reply

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 🙂