LeetCode二叉树展开为链表递归解法指针操作逻辑疑问

题目要求将给定二叉树原地展开为单链表结构，题目给出的初始代码框架如下：

# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """

class Solution:

    def flattenTree(self, node):

        # 处理空节点场景
        if not node:
            return None

        # 叶子节点直接返回自身
        if not node.left and not node.right:
            return node

        # 递归展开左子树
        leftTail = self.flattenTree(node.left)

        # 递归展开右子树
        rightTail = self.flattenTree(node.right)

        # 如果存在左子树，调整指针连接，清空左指针
        if leftTail:
            leftTail.right = node.right
            node.right = node.left
            node.left = None

        # 返回调整完成后当前子树的最右节点
        return rightTail if rightTail else leftTail

    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        self.flattenTree(root)

无法理解以下3行指针调整逻辑的执行顺序：

if leftTail:
    leftTail.right = node.right # step1
    node.right = node.left      # step2
    node.left = None

以输入二叉树[1,2,3]（根节点1，左孩子2，右孩子3）为例：执行step1后leftTail对应节点2的结构为[2, null, 3]，原本以为执行step2后树结构会变成[1, null, 3]，但实际运行结果是[1,null,2,null,3]，需要明确这段代码的实际执行逻辑。

误解核心是混淆了指针存储的引用对象，这3行代码的本质是把展开后的左子树整体插到当前节点和原右子树之间，我们拿输入[1,2,3]的执行过程逐行拆解：
递归执行到根节点1时，前置递归已经完成左右子树的展开：

• 左子树只有叶子节点2，因此leftTail = 2
• 右子树只有叶子节点3，因此rightTail = 3
  此时三个节点的初始指针状态：
• 节点1：left=2，right=3
• 节点2：left=None，right=None
• 节点3：left=None，right=None

接下来执行三行调整逻辑：

• 执行step1 leftTail.right = node.right：把左子树尾节点（节点2）的右指针，指向当前节点的原右节点（节点3）。执行完后节点2的结构为[2, null, 3]，这一步的作用是把原右子树接到左子树的最末尾，避免原右子树的引用丢失。
• 执行step2 node.right = node.left：把当前节点（节点1）的右指针，从原来指向3，修改为指向自己的左孩子节点2。注意这一步只是修改节点1的右指针指向，不会改动节点2本身的结构，节点2的右指针仍然指向3。执行完后指针链已经变成1->2->3。
• 执行node.left = None：把当前节点的左指针置空，符合题目要求的单链表全右指针结构，最终得到的展开结果就是[1,null,2,null,3]。

这三步的通用逻辑可以直接套用到所有节点场景：

• 第一步：找左子树的最右尾节点，把原右子树挂到这个尾节点的右指针上
• 第二步：把当前节点的右指针替换为展开完成的左子树头节点（原左孩子）
• 第三步：清空当前节点的左指针

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