孩子长大后，说父亲是一名程序员，会不会很丢人？

不得不说，网上人才是真的多啊，这不，又让我刷到一个灵魂发问：孩子长大后，知道自己爸是程序员，会不会觉得丢人？嚯，这问题我第一反应是，这谁家孩子啊，管这么宽！

底下网友回复也挺有意思，有的说你想多了，等娃大了你可能都不写代码了，估计在送外卖，哈哈，嘴真毒！也有人说张一鸣不也是程序员出身，英雄不问出处，这话听着舒服。还有网友劝别太在意别人的看法，这确实，咱活这么大，难道还为别人活？

我觉得吧，程序员怎么了？白天写代码，晚上修bug，靠自己本事吃饭，有啥丢人的？你娃长大了，看到你靠技术养家，说不定还挺骄傲。最怕的不是职业丢人，是自己都看不起自己。所以啊，心态放平点，码农也挺香的！

不得不说，程序员的世界里，最能体现内功修为的，还得是刷算法题。这不，最近碰到个挺有意思的老朋友：二叉树展开为链表。听上去就像是把一棵枝繁叶茂的大树削成一根竹竿，咱说干就干。

题目其实很简单粗暴，给你一棵二叉树，让你原地把它变成一条单向链表（按照前序遍历的顺序）。说到“原地”，程序员的DNA就动了，这是要优化空间复杂度的意思，不能瞎开新空间糊弄过去，得真刀真枪上。

我一看，二叉树，前序遍历，展开成链表，这不就先走根节点，再左子树，再右子树嘛。第一反应是写个前序遍历，拿个列表把节点全存起来，最后一个个重新接起来，空间复杂度 O(n)，简单粗暴。但是，题目说了，原地。老实说，刷题这么多年，我对这种题的空间复杂度要求已经PTSD了，看到“原地”就条件反射：栈、递归、Morris 遍历，翻来覆去那点活。

所以，最直接的方法——递归走起。逻辑其实也不绕：

1. 先处理左子树，把左子树展平成链表。
2. 再处理右子树。
3. 然后把左子树接到右子树的位置，右子树拼到最右边。

听着挺抽象？贴点代码：

classSolution:
defflatten(self, root):
ifnot root:
return

# 递归处理左右子树
        self.flatten(root.left)
        self.flatten(root.right)

# 临时保存左子树和右子树
        left = root.left
        right = root.right

# 左子树接到右子树位置
        root.left = None
        root.right = left

# 找到原来左子树的最右节点，把右子树接上
        p = root
while p.right:
            p = p.right
        p.right = right

这段代码一看就很“程序员”，思路直白，操作粗暴，递归到底。不过吧，这代码虽然思路清晰，但说实话，它每次都要遍历左子树的最右节点，有点耗时，不够优雅，典型的能用但不够快。

于是更骚的解法来了：Morris 遍历。什么叫Morris？不新开栈，不用递归，靠指针自己绕，空间复杂度 O(1)。就是在树的节点间来回折腾，自己把自己掏空。用这个搞定“原地”展开，才是稳稳的性能拉满：

classSolution:
defflatten(self, root):
        curr = root
while curr:
if curr.left:
# 找左子树的最右节点
                predecessor = curr.left
while predecessor.right:
                    predecessor = predecessor.right
# 把当前节点的右子树接到前驱节点的右边
                predecessor.right = curr.right
# 左子树接到右边
                curr.right = curr.left
                curr.left = None
# 继续下一个节点
            curr = curr.right

Morris 的思路其实有点像拆东墙补西墙，左子树找到最右节点，把右子树接上去，再把左子树塞到右边，左边清空，继续往下撸。整棵树被拆成一条链，空间复杂度 O(1)，时间复杂度 O(n)，又快又省。

我每次刷完这种题，脑子里总浮现一个画面：二叉树被拆成一条链，节点们一个个挪屁股到右边，最后留下个干净利落的右指针链表。至于这道题到底用递归还是Morris？我觉得得看心情，递归写得舒服，Morris跑得快，各有千秋。

不过说实话，Morris 这种操作，第一次看还是有点上头的，折腾多了，就觉得不过如此。这不就是代码界的空间魔术嘛，连指针都玩出了花，真·内功深厚。