这段代码实现了将二叉树“原地”展开为链表的算法（LeetCode 114. Flatten Binary Tree to Linked List）。它采用的是一种空间复杂度为 $O(1)$ 的巧妙方法，即利用 “寻找前驱节点” 的逻辑。

---

1. 代码逐行注释

C++

class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* cur = root; // 从根节点开始遍历
        
        while (cur != nullptr) {
            // 如果当前节点有左子树，说明需要进行“剪切和重接”
            if (cur->left != nullptr) {
                
                // --- 寻找左子树的最右节点（即当前节点的中序遍历前驱节点） ---
                TreeNode* predecessor = cur->left;
                while (predecessor->right != nullptr) {
                    predecessor = predecessor->right;
                }
                
                // --- 核心重组逻辑 ---
                // 1. 将当前节点的右子树，接到左子树最右节点的右边
                predecessor->right = cur->right;
                
                // 2. 将整个左子树移到右边
                cur->right = cur->left;
                
                // 3. 将左子树清空（因为已经移到了右边）
                cur->left = nullptr;
            }
            
            // 继续处理下一个右节点（可能是原有的右节点，也可能是刚移过来的左子树根节点）
            cur = cur->right;
        }
    }
};

---

2. 设计思路：拼接“断层”

这个算法的精髓在于：要把原本在左边的内容，插到当前节点和它的右子树之间。

为了保持先序遍历（根-左-右）的顺序：

1. 我们必须找到左子树中“最后一个”被访问的节点。

2. 在先序遍历中，左子树的最后一个节点就是左子树里最靠右的那个叶子。

3. 把原来的 cur->right 挂到这个叶子的右边，这样就保证了遍历的连续性。

---

3. 运行步骤演示

假设有这样一棵树：

Plaintext

    1
   / \
  2   5
 / \   \
3   4   6

第一轮循环 (cur 指向 1):

• 检测：1 有左子树（以 2 为根）。

• 寻找前驱：从 2 开始向右找，找到左子树的最右节点是 4。

• 重组：

  • 把 1 的右子树（5-6）接到 4 的右边。

  • 把 1 的左子树（2-3-4）整体移到 1 的右边。

  • 1 的左边置为空。

• 结果：

  Plaintext

  1
   \
    2
   / \
  3   4
       \
        5
         \
          6
  

第二轮循环 (cur 指向 2):

• 检测：2 有左子树（3）。

• 寻找前驱：3 没有右孩子，前驱就是 3。

• 重组：把 2 的右子树（4-5-6）接到 3 的右边。

• 结果：

  Plaintext

  1 - 2 - 3 - 4 - 5 - 6 （形成单链表结构）
  

---

4. 复杂度分析

• 时间复杂度：$O(N)$。虽然有嵌套循环，但每个边缘（Edge）最多只被访问两次（一次寻找前驱，一次遍历）。

• 空间复杂度：$O(1)$。没有使用递归栈，也没有额外的辅助容器，这是该方法最大的优点。