Python sortAPI Sorting Techniques — Python 3.14.2 documentation
0x3F also need to special check if ans is None, it is essencial
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key = lambda interval: interval[0]) # sort in place
if not intervals:
return []
ans = [intervals[0]]
for interval in intervals:
# only see the last one with interval, ensure the correctness with induction
# integrate or append
if ans[-1][1] >= interval[0]:
ans[-1][1] = max(ans[-1][1], interval[1])
else:
ans.append(interval)
return ans
# 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 diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
ans = 0
def maxDepth(root) -> int:
if root is None:
return -1 # leaf is 0, then None should be -1
DepthLeft = maxDepth(root.left) + 1 # count from left to root
DepthRight = maxDepth(root.right) + 1
nonlocal ans
ans = max(ans, DepthLeft + DepthRight)
return max(DepthLeft, DepthRight)
maxDepth(root)
return ans
Non-local
excerpt from 9. Classes — Python 3.14.2 documentation
The local namespace for a function is created when the function is called, and deleted when the function returns or raises an exception that is not handled within the function. (Actually, forgetting would be a better way to describe what actually happens.) Of course, recursive invocations each have their own local namespace.
A scope is a textual region of a Python program where a namespace is directly accessible. “Directly accessible” here means that an unqualified reference to a name attempts to find the name in the namespace.
directly accessible：就是你直接写 x，而不是写 math.x 或者 self.x。
unqualified reference：不带点号（.）的变量名。
Although scopes are determined statically, they are used dynamically. At any time during execution, there are 3 or 4 nested scopes whose namespaces are directly accessible:
the innermost scope, which is searched first, contains the local names
the scopes of any enclosing functions, which are searched starting with the nearest enclosing scope, contain non-local, but also non-global names
the next-to-last scope contains the current module’s global names
the outermost scope (searched last) is the namespace containing built-in names
解释（LEGB 法则）：
当你在代码里用了一个变量名 x，Python 会像剥洋葱一样，从内向外一层层找：
L (Local): 你的函数内部。
E (Enclosing): 如果你在函数里又写了一个函数，那外层函数的区域就是 Enclosing。
G (Global): 当前 .py 文件定义的全局变量。
B (Built-in): Python 自带的函数，比如 len, print, int。
If a name is declared global, then all references and assignments go directly to the next-to-last scope containing the module’s global names. To rebind variables found outside of the innermost scope, the nonlocal statement can be used; if not declared nonlocal, those variables are read-only ( an attempt to write to such a variable will simply create a new local variable in the innermost scope, leaving the identically named outer variable unchanged).
只要你想在函数内部对一个不在当前函数定义的变量进行“赋值操作”（即使用 = 修改指向），你就必须先在函数内用一行代码单独声明它。
Validate Binary Search Tree
leetcode Test Problem:
Leetcode's judging System typically intantiates the Solution class once and reuses the same instance on several test cases. So pre may not be -inf in some cases
so if the pre is an attribute of Solution, it is dangerous
# 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:
pre = -inf
def isValidBST(self, root: Optional[TreeNode]) -> bool:
# inorder sequence is strictly increaing <=> this tree is a valid BST
# so just traverse the tree in order and check if root > pre
if root is None: # this means we cross the leaf, it doesn't bigger than pre, we should special check it
return True
left = self.isValidBST(root.left) # inorder traverse with a bool return value represent if it is a ValidBST
if left is False: # the False we return in the inner function should be handle
return False
if root.val <= self.pre:
return False
self.pre = root.val
right = self.isValidBST(root.right)
if right is False:
return False
else:
return True
To avoid this situation, we need to initialize pre every time isValidBST is called, but maintain pre's value in the traverse process.
so we make pre a local variable in isValidBST, and the recursion logic a nested function in isValidBST against inproperly reset during recursion
When you are writing recursion function, how to deal with return value of sub recursion is important. If you don't make it clear, you can not write the correct code.
For example, Many standard recursion problem followed this pattern: the final result is correct if and only if all sub problem return True AND a little check like the sub-recursion
105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if len(preorder) == 0 or len(inorder) == 0:
return
root = preorder[0]
root_index = inorder.index(root)
# get inorder
inorder_left = inorder[:root_index]
inorder_right = inorder[root_index + 1:]
# get preorder with len
preorder_left = preorder[1:len(inorder_left) + 1]
preorder_right = preorder[len(inorder_left) + 1:]
left = self.buildTree(preorder_left, inorder_left)
right = self.buildTree(preorder_right, inorder_right)
return TreeNode(root, left, right)
思路：发现构建大树需要用相同的方法构建子树，因此可以使用递归
the most confusing point in this question is the whether to +1, the Planting Tree Problem
Slicing: list[a:b] get list[a] list[a + 1] --- list[b - 1], left close right open, total amount is b - a
if the start index of list is a(included), len(list) == l, the end index is a + l - 1(included), or
a + l(included)
Useless deduction: if you devide a continuous list into two list with Slicing, it should be like [a, b] [b, c]. The end of list1 == start of list2