二叉树扁平化代码疑问：为何默认值需设为None而非当前节点？

你的核心疑问在于：为什么leftmostofright和rightmostofleft必须初始化为None，而不能设为当前node？我们从变量含义、链表连接逻辑、错误场景三个层面拆解：

一、明确每个变量的实际作用 #

helper函数的核心是返回当前子树扁平化后的最左节点和最右节点，初始化的变量是为了处理「当前节点无左/右子树」的边界情况：

• leftmostofleft：当前节点左子树的最左节点，无左子树时，当前节点就是左子树的起点，所以初始化为node
• rightmostofright：当前节点右子树的最右节点，无右子树时，当前节点就是右子树的终点，所以初始化为node
• rightmostofleft：当前节点左子树的最右节点，只有存在左子树时才有意义，无左子树时不存在这个节点，因此必须初始化为None
• leftmostofright：当前节点右子树的最左节点，只有存在右子树时才有意义，无右子树时不存在这个节点，因此必须初始化为None

二、为什么不能初始化为node？ #

看代码里的关键连接逻辑：

# 连接当前节点和左子树的末尾
node.left = rightmostofleft
if rightmostofleft:
    rightmostofleft.right = node

# 连接当前节点和右子树的开头
node.right = leftmostofright
if leftmostofright:
    leftmostofright.left = node

1. 无左子树的场景：
   如果把rightmostofleft初始化为node，会执行node.left = node，让当前节点的left指针指向自己，形成循环引用。同时if rightmostofleft条件成立，会执行rightmostofleft.right = node，也就是node.right = node，彻底破坏双向链表结构——遍历到这个节点时会无限循环，无法继续访问其他节点。

2. 无右子树的场景：
   如果把leftmostofright初始化为node，会执行node.right = node，同样形成循环。if leftmostofright条件成立后，leftmostofright.left = node会让node.left = node，同样导致遍历死循环。

三、正确初始化的必要性 #

当节点无左子树时，rightmostofleft为None，执行node.left = None符合双向链表逻辑：链表头节点左侧没有节点；
当节点无右子树时，leftmostofright为None，执行node.right = None也符合逻辑：链表尾节点右侧没有节点。

同时，if rightmostofleft:和if leftmostofright:的条件判断会自动跳过无对应子树时的连接操作，避免无效的指针赋值。

附可运行代码 #

实现代码 #

class BinaryTree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def flattenBinaryTree(root):
    a, b = helper(root)
    return a


def helper(node):
    if node is None:
        return None, None
    if node.left is None and node.right is None:
        return node, node
    leftmostofleft = node
    rightmostofright = node
    leftmostofright = None
    rightmostofleft = None
    if node.left:
        leftmostofleft, rightmostofleft = helper(node.left)
    if node.right:
        leftmostofright, rightmostofright = helper(node.right)

    node.right = leftmostofright
    if leftmostofright:
        leftmostofright.left = node
    node.left = rightmostofleft
    if rightmostofleft:
        rightmostofleft.right = node

    return leftmostofleft, rightmostofright

测试代码 #

import program
import unittest


class TestProgram(unittest.TestCase):
    def test_case_1(self):
        root = BinaryTree(1).insert([2, 3, 4, 5, 6])
        root.left.right.left = BinaryTree(7)
        root.left.right.right = BinaryTree(8)
        leftMostNode = program.flattenBinaryTree(root)
        leftToRightToLeft = leftMostNode.leftToRightToLeft()
        expected = [4, 2, 7, 5, 8, 1, 6, 3, 3, 6, 1, 8, 5, 7, 2, 4]
        self.assertEqual(leftToRightToLeft, expected)


class BinaryTree(program.BinaryTree):
    def insert(self, values, i=0):
        if i >= len(values):
            return
        queue = [self]
        while len(queue) > 0:
            current = queue.pop(0)
            if current.left is None:
                current.left = BinaryTree(values[i])
                break
            queue.append(current.left)
            if current.right is None:
                current.right = BinaryTree(values[i])
                break
            queue.append(current.right)
        self.insert(values, i + 1)
        return self

    def leftToRightToLeft(self):
        nodes = []
        current = self
        while current.right is not None:
            nodes.append(current.value)
            current = current.right
        nodes.append(current.value)
        while current is not None:
            nodes.append(current.value)
            current = current.left
        return nodes

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