共计 2808 个字符，预计需要花费 8 分钟才能阅读完成。
ARTS
ARTS 是陈浩（网名左耳朵耗子）在极客时间专栏里发起的一个活动，目的是通过分享的方式来坚持学习。
每人每周写一个 ARTS：Algorithm 是一道算法题，Review 是读一篇英文文章，Technique/Tips 是分享一个小技术，Share 是分享一个观点。
本周内容
本周的 ARTS 你将看到：
- 经典题「树中节点的最低公共祖先」
- 一个 Golang 多队列的 worker-dispatcher 原型
- 关于编程的方法论
Algorithm
这周的算法题是「树中节点的最低公共祖先」。
[235. Lowest Common Ancestor of a Binary Search Tree
](https://leetcode.com/problems…
[236. Lowest Common Ancestor of a Binary Tree
](https://leetcode.com/problems…
这两道题相同之处都是需要求公共祖先，但不同的是「二叉树」还是「二叉查找树」的最低公共祖先。对于二叉树，只能通过后序遍历来求。但是如果给出的两个节点如果互为父子的话，就无法通过简单的后序遍历来判断了，需要单独判断。这种方法对于任何的二叉树都是适用的，当然也包含二叉查找树 BST. 如果对 BST 的公共祖先也是用这种方式的话，因为没有利用 BST 本身的排序特性，必然时间复杂度上会吃亏。话不多说，直接上代码吧，欢迎拍砖。
先是普通二叉树节点的最低公共祖先代码。
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
// dfs 函数里的逻辑没办法包含 p q 互为父子的情况
// 这里只能单独判断
if isAcst(p, q) {return p}
if isAcst(q, p) {return q}
var ans *TreeNode
var dfs func(node, p, q *TreeNode) (bool, bool)
dfs = func(node, p, q *TreeNode) (bool, bool) {
if node == nil {return false, false}
leftFoundP, leftFoundQ := dfs(node.Left, p, q)
rightFoundP, rightFoundQ := dfs(node.Right, p, q)
foundP, foundQ := leftFoundP || rightFoundP, leftFoundQ || rightFoundQ
// 因为是后序遍历，暂时想不到很好的剪枝办法
if ans == nil && (foundP && foundQ) {
ans = node
return true, true
}
if node == p {foundP = true}
if node == q {foundQ = true}
return foundP, foundQ
}
fp, fq := dfs(root, p, q)
if ans == nil && (fp && fq) {ans = root}
return ans
}
// return p if p is ancestor of q
func isAcst(p, q *TreeNode) bool {
var found bool
var find func(node *TreeNode)
find = func(node *TreeNode) {
if node == nil {return}
if found {return}
if node == q {
found = true
return
}
find(node.Left)
find(node.Right)
}
find(p)
return found
}然后是 BST 中节点的最低公共祖先。
// 首先这是一棵 BST 祖先节点的值
// 利用 BST 的性质，祖先节点的 Val 介于 p.Val q.Val 之间
// 反之，如果不介于二者之间的值是 p q 的祖先节点，那么一定存在更底层的祖先节点
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
var ans *TreeNode
node := root
for !in(node, p, q) {
if node == nil {break}
if node.Val > max(p, q).Val {node = node.Left}
if node.Val < min(p, q).Val {node = node.Right}
}
if node != nil {ans = node}
return ans
}
func in(node, p, q *TreeNode) bool {return node.Val >= min(p, q).Val && node.Val <= max(p, q).Val
}
func min(p, q *TreeNode) *TreeNode {
if p.Val < q.Val {return p}
return q
}
func max(p, q *TreeNode) *TreeNode {
if p.Val > q.Val {return p}
return q
}Review 文章推荐
本周的文章推荐是 Handling 1 Million Requests per Minute with Golang. 文中介绍了一个高并发场景下的 Golang 多队列的 worker-dispatcher 模式原型，虽然是很久之前的文章，但目前来看类似的 w-d 模型依然大同小异。
但是跳出条框的舒服，上面文中的多队列方式的 workerpool 和各种 channel 入门中提到的单队列方式（一个协程写 chan 多个协程并发读 chan）的根本区别是什么呢？
我目前的直观感受就是，高并发的情况都各队列的 chan 就能多缓存一些 job（这里指使用 chan 的 buffer），相比单队列 chan 在高并发量的情况下更不容易出现 chan 满导致拒绝 job 请求。但我想这应该是在 cpu 处理能力足够的前提下，如果 cpu 处理能力本身就不足那就谈不上多队列更高效这种可能。
其实类似的问题有很多，这种问题无法用公式和算法之类的东西确切描述，像极了常说的「经验」。但是开发人员一般都是更愿意想相信专家而不是经验，这就很有意思了。
Tip 编程技巧
本周依然没有技巧。嚎啕大哭。
Share 灵光一闪
这一周的灵光一闪是关于上面文章中提到的关于编程中那些「经验」的一些看法。这些经验经常可以在分布式系统以及操作系统中找到，多数时候乍一看感觉非常正确，但有无法给出公式般准确的推导过程。给人一种既神秘又强大的感觉，以我目前的 conding 能力还很难掌握这些经验。甚至在未来的某个阶段这些经验会是我最需要学习的东西，这都很难说。
我暂时把这些「经验」叫做编程之禅。
本周阅读列表
Go 语言设计与实现
官方对 defer panic 和 recover 的介绍
官方 Go Concurrency Patterns: Timing out, moving on
文中的观点，select case 的方式等待 chan 的可读或者可写时，如果使用了 default 分支的话，就相当于非阻塞？
Handling 1 Million Requests per Minute with Golang
