LeetCode #94 二叉树中序遍历代码中tmp变量的作用是什么

你所提供的代码是二叉树中序遍历的Morris遍历实现，这种算法不需要额外栈存储空间，空间复杂度为O(1)。你提到的tmp相关两行代码核心作用是切断当前节点和左子树的关联，避免遍历过程中出现环，从而防止死循环超时。

具体逻辑拆解： #

当处理存在左子树的节点root时，代码会先完成两个前置操作：

• 找到root左子树的最右节点pre，将pre.right指向root，相当于给左子树遍历完之后搭一个跳回当前节点的桥
• 把root移动到左子节点，继续遍历左子树

如果没有tmp = root和tmp.left = None这两行：
当后续遍历完左子树，通过之前搭的桥跳回原root节点时，程序会再次检测到该节点存在左子树，又会重复执行「找左子树最右节点」的逻辑。此时因为之前已经把左子树最右节点的right指向了原root，找最右节点的循环会在原root和左子树之间无限执行，最终触发超时错误。

tmp的作用就是暂存原root节点的引用：Python中对象是引用传递，tmp和修改前的root指向同一个二叉树节点对象，修改tmp.left本质就是修改原节点的左子树指针，不需要把tmp用到其他地方也能生效。将原节点的left置为None后，后续再次访问到该节点时就不会重复处理左子树，也就不会出现死循环。

内容的提问来源于stack exchange，提问作者user900476