LeetCode叶子相似树问题：无并发O(1)空间顺序解法问询

嘿，很高兴看到你已经挖透了Morris遍历这个关键点——这确实是实现O(1)空间树遍历的核心！你担心无并发情况下做不到？答案是完全可以，咱们只需要把两个Morris遍历改成分步迭代的形式，每次从两棵树里各取出下一个叶子节点就立刻对比，全程不需要存储任何叶子序列。

核心思路 #

并发版里你用channel同步两个遍历的叶子输出，顺序版的话，我们可以为每棵树维护Morris遍历的当前状态（当前节点、前驱节点、遍历所处的阶段），然后写一个辅助函数：每次调用它，就推进对应树的Morris遍历，直到找到下一个叶子节点，然后暂停遍历、保存状态，返回这个叶子值。这样我们就能循环调用这个函数，拿到两棵树的叶子节点就直接对比，一旦发现不一致或者数量不等，立刻返回结果。

具体实现代码 #

首先，我们需要一个结构体来保存Morris遍历的状态：

type morrisState struct {
    curr *TreeNode
    pre  *TreeNode
    // 标记当前遍历的步骤，避免每次从头开始
    // 0: 初始状态，准备处理当前节点的左子树
    // 1: 已经找到前驱，准备恢复指针并处理右子树
    step int
}

然后写一个辅助函数，负责从指定的Morris状态中获取下一个叶子节点：

func nextLeaf(state *morrisState) (int, bool) {
    for state.curr != nil {
        switch state.step {
        case 0:
            if state.curr.Left == nil {
                // 当前节点没有左子树，直接检查是否是叶子
                if state.curr.Right == nil {
                    val := state.curr.Val
                    state.curr = state.curr.Right
                    return val, true
                }
                state.curr = state.curr.Right
            } else {
                // 找左子树的最右节点（前驱）
                state.pre = state.curr.Left
                for state.pre.Right != nil && state.pre.Right != state.curr {
                    state.pre = state.pre.Right
                }
                if state.pre.Right == nil {
                    // 建立临时链接，转向左子树
                    state.pre.Right = state.curr
                    state.curr = state.curr.Left
                } else {
                    // 已经访问过左子树，准备恢复链接
                    state.step = 1
                }
            }
        case 1:
            // 恢复前驱节点的右指针
            state.pre.Right = nil
            // 这里要注意：前驱节点如果是叶子（左子树为空），它就是我们要找的叶子
            if state.pre.Left == nil {
                val := state.pre.Val
                state.curr = state.curr.Right
                state.step = 0
                return val, true
            }
            state.curr = state.curr.Right
            state.step = 0
        }
    }
    // 没有更多叶子了
    return 0, false
}

最后是主函数，初始化两个树的遍历状态，循环对比叶子节点：

func leafSimilar(root1 *TreeNode, root2 *TreeNode) bool {
    // 初始化两棵树的Morris遍历状态
    state1 := &morrisState{curr: root1, step: 0}
    state2 := &morrisState{curr: root2, step: 0}

    for {
        val1, ok1 := nextLeaf(state1)
        val2, ok2 := nextLeaf(state2)

        // 两种不一致的情况：叶子数量不等，或者叶子值不同
        if ok1 != ok2 || (ok1 && val1 != val2) {
            return false
        }
        // 两棵树都没有更多叶子了，说明完全一致
        if !ok1 && !ok2 {
            return true
        }
    }
}

关键细节说明 #

1. 状态保存：通过morrisState结构体，我们可以暂停Morris遍历的进度，下次调用nextLeaf时从上次暂停的地方继续，不需要从头遍历树。
2. 叶子节点检测：和你之前的并发版逻辑一致，除了处理左子树为空的节点时检查是否是叶子，还要在恢复前驱节点的右指针时，判断前驱节点是否是叶子（这是Morris遍历中容易遗漏的叶子节点）。
3. 空间复杂度：整个过程只用到了两个morrisState结构体，每个结构体只有三个字段（两个指针+一个整数），属于O(1)常数空间，完全符合要求。

关于可行性的确认 #

你之前怀疑无并发做不到，其实核心是把“异步生成叶子”改成“同步分步生成叶子”——通过保存遍历状态，我们可以像迭代器一样，每次从两棵树里“取出”一个叶子，对比后再继续，完全不需要中间存储，也不需要并发。

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