CodingTour —
ARTS #151

Algorithm

本周选择的算法题是：Recover Binary Search Tree。

规则

You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

Example 1:

img

Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

Example 2:

img

Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.

Constraints:

  • The number of nodes in the tree is in the range [2, 1000].
  • -231 <= Node.val <= 231 - 1

Follow up: A solution using O(n) space is pretty straight-forward. Could you devise a constant O(1) space solution?

Solution

class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        cur, prev, drops, stack = root, TreeNode(float('-inf')), [], []
        while cur or stack:
            while cur:
                stack.append(cur)
                cur = cur.left
            node = stack.pop()
            if node.val < prev.val: drops.append((prev, node))
            prev, cur = node, node.right
        drops[0][0].val, drops[-1][1].val = drops[-1][1].val, drops[0][0].val

Review

Python 3.11 is Coming! Here’s How It Fares Against Python 3.10

3.11 干货不多，主要是对开发体验的完善：

  1. 错误输出更直观
  2. typing 模块增加了 Self 类型注解
  3. BaseException 增加了一个额外的 note 字段描述异常信息
  4. 增加了 ExceptionGroup 以便一次抛出多个异常，except 语法也变复杂了，实际用处大吗？
  5. List Comprehension 支持嵌套 async
  6. TOML 格式解析集成进了标准库

相比之下，Python 3.11 vs 3.10 对不同模块有 10~60% 的性能提升，算是有一点实质性的优化。

Tip

set -o pipefail，在管道命令中非常好用，返回第一个非零返回值，防止错误状态码被吃掉。

Share

越是敏感的人，越要学会与自己和解，与现实和解，学会放手。这需要格局的提升，也没有特别有效的方法。

「子在川上曰，逝者如斯夫」。

只要你在河流边待过，曾经凝望过河流，会知道这是怎样的场景。

任何事情、任何人，包括我们自己在内，无论我们多么在意，都与我们眼前的这条河流一样，滚滚向前，不会有片刻留恋。