深入理解二叉树展平：原地算法与递归艺术的完美结合

2026-02-15 16:53:29 0条评论 1次阅读 0人点赞

在算法面试和实际开发中，处理树形结构是非常常见的需求。今天，我们将深入探讨一个经典且极具挑战性的问题——将二叉树展平为链表。

这不仅仅是一道算法题，更是一次对指针操作、递归思维以及树结构遍历的深度演练。当我们谈论“展平”时，我们的目标是将一棵复杂的二叉树转换成一个“伪”链表：其中原本的 INLINECODEb9e36a88 指针变成了链表的 INLINECODEdbfb542b 指针，指向下一个节点；而原本的 left 指针则全部被置为空。

在这篇文章中，你将学到如何在不使用额外数据结构（如队列或数组）的情况下，利用递归和指针操作“原地”完成这项工作。我们不仅会分析代码的每一个细节，还会探讨潜在的陷阱和优化思路，帮助你彻底掌握这一技巧。

问题陈述与基本概念

首先，让我们明确一下目标。给定一棵二叉树，我们需要按照前序遍历（根-左-右）的顺序，将其重新组织。展平后的链表，其 INLINECODE97db8127 指针应指向前序遍历中的后继节点，而 INLINECODE9f60f252 指针必须为 NULL。

#### 让我们看一个直观的例子：

示例 1：

这是一个标准的二叉树结构：

    输入：
          1
        /   \
       2     5
      / \     \
     3   4     6

经过展平后，前序遍历的顺序是 1 -> 2 -> 3 -> 4 -> 5 -> 6。我们需要改变指针来反映这一顺序：

    输出：
    1
     \
      2
       \
        3
         \
          4
           \
            5
             \
              6

示例 2：

再看一个稍微复杂一点的情况，展示了节点的左孩子在展平后如何移动到右侧：

    输入：
        1
       / \
      3   4
         /
        2
         \
          5

展平后的顺序是 1 -> 3 -> 4 -> 2 -> 5。请注意观察节点 2 和 5 的位置变化：

    输出：
     1
      \
       3
        \
         4
          \
           2
            \ 
             5

探索解决方案：从简单到高效

在深入最优解之前，让我们先看看那些“虽然可行但不够完美”的方案，这有助于我们理解为什么最终选择的方法更加优雅。

#### 方法一：简单但空间复杂度较高的方案

我们可以很容易地想到一种思路：先进行一次完整的前序遍历，将所有节点按顺序存储在一个队列或数组中，然后遍历这个列表，依次修改节点的指针。

  • 优点：逻辑非常简单，不容易出错。
  • 缺点：我们需要 O(N) 的额外空间来存储节点。如果题目要求是“原地”操作或者对空间复杂度有严格限制，这种方法就不符合要求了。虽然题目允许使用递归栈空间，但显式使用队列通常被认为是非最优解。

#### 方法二：高效的原地递归法（推荐）

为了满足 O(1) 的额外空间复杂度（不考虑递归栈），我们需要直接在树上进行操作。核心思想是利用递归的特性：先处理子树，再将子树的结果拼接到当前节点上。

核心算法逻辑：

我们可以采用 “左子树前插法”。对于当前节点 root：

  • 递归左子树：首先，我们假设 root->left 已经被展平成了一条链表。这是递归的魅力所在，我们不需要担心内部细节，只需假设它已经完成。
  • 处理左子树连接：如果左子树存在，我们需要把它移到右边。

* 保存当前的右子树（INLINECODE17ae59ca）到临时变量 INLINECODE1be6524e，因为我们需要把这部分内容接到移动后的左子树的末尾。

* 将 INLINECODE31769690 指向 INLINECODEccbdce6d（即把左子树挪到右边）。

* 将 INLINECODE438e03d9 设为 INLINECODE3c5578d4（符合题目要求）。

  • 寻找插入点：现在，原本的左子树已经变成了 root 的右孩子。我们需要找到这个新右子链表（即原本的左子树）的最后一个节点。因为展平后的链表是单向的，我们需要遍历到该链表的末端。
  • 拼接原右子树：找到末端节点后，将第2步中保存的 INLINECODE2c7597a6 接在这个末端节点的 INLINECODE1248f4c3 指针上。
  • 递归右子树：现在，当前节点的左右结构已经调整完毕，我们继续对当前节点的新右子树（即刚才拼接好的整体）进行同样的展平操作。

图解过程：

想象一下上面的示例 1，节点 INLINECODEafc4978b 有左孩子 INLINECODEd8021650 和右孩子 5。

  • 我们先递归处理左边的 INLINECODE69482c8e。递归结束后，这部分变成了 INLINECODE8b843c17 的链表。
  • 此时回到节点 INLINECODEf8d30e0f。我们将 INLINECODE2fd32731 的右指针指向 INLINECODEf697d16e，左指针置空。现在 INLINECODEf0bf06f5 连着 INLINECODE3b7f66a9，而原来的右子树 INLINECODE8b2246da 暂时存在变量里。
  • 我们顺着 INLINECODE2023738b 往下走，发现 INLINECODEb074b7bb 是尽头。
  • 把 INLINECODE45847fcf 接到 INLINECODE768f2540 的后面。变成 1->2->3->4->5->6。
  • 递归继续处理后续节点。

代码实现与深度解析

让我们把上述逻辑转化为代码。我们将使用 C++ 和 C 两种语言来实现，并添加详细的注释以帮助理解。

#### C++ 实现

C++ 提供了强大的标准库和清晰的语法，非常适合实现这类指针操作。

// C++ 程序：将二叉树原地展平为链表
// 利用递归和指针操作实现

#include 
using namespace std;

// 定义树节点结构体
struct Node {
    int key;          // 节点存储的数据
    Node *left, *right; // 左右子节点指针
};

// 工具函数：创建一个新节点
Node* newNode(int key)
{
    Node* node = new Node;
    node->key = key;
    node->left = node->right = NULL;
    return (node);
}

// 核心函数：将二叉树展平
// 逻辑：前序遍历的展开，左子树变为右子树，原右子树接到末尾
void flatten(struct Node* root)
{
    // 基本条件：如果根节点为空，或者是叶子节点（没有左右孩子），直接返回
    if (root == NULL || (root->left == NULL && root->right == NULL))
        return;

    // 1. 如果左子树存在，我们需要将其处理并移动到右边
    if (root->left != NULL) {
        // 递归调用，先展平左子树
        // 递归保证了 root->left 变成了一条只有 right 指针的链表
        flatten(root->left);

        // 保存当前的右子节点，因为接下来我们要修改 root->right
        struct Node* tmpRight = root->right;
        
        // 将左子树移动到右子树的位置
        root->right = root->left;
        // 左指针必须置空，满足链表要求
        root->left = NULL;

        // 2. 寻找新右子树（原左子树）的最后一个节点
        // 因为我们已经把左子树移到了右边，所以从 root->right 开始遍历
        struct Node* current = root->right;
        while (current->right != NULL) {
            current = current->right;
        }
        
        // 3. 将原本保存的右子树接到新链表的末尾
        current->right = tmpRight;
    }

    // 4. 递归处理当前节点的新右子树
    // 注意：此时 root 的结构已经发生了变化，我们需要继续处理剩下的部分
    flatten(root->right);
}

// 辅助函数：中序遍历打印树
// 用于验证展平后的结果，展平后的树中序遍历应该是一个递减序列吗？
// 不，展平后的树没有左孩子，所以中序遍历就是按 right 指针顺序访问
void inorder(struct Node* root)
{
    if (root == NULL)
        return;
    inorder(root->left); // 展平后这里总是 NULL
    cout <key <right);
}

/* 主函数用于测试 */
int main()
{
    /* 构建示例树：
          1
        /   \
       2     5
      / \     \
     3   4     6
    */
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(5);
    root->left->left = newNode(3);
    root->left->right = newNode(4);
    root->right->right = newNode(6);

    // 调用展平函数
    flatten(root);

    cout << "展平后的二叉树遍历输出: ";
    inorder(root);
    // 预期输出: 1 2 3 4 5 6
    
    return 0;
}

#### C 语言实现

C 语言是理解底层内存管理的最佳方式。虽然没有类，但通过结构体和指针，我们能更清晰地看到每一个字节的变化。

// C 程序：将二叉树展平为链表
#include 
#include 

// 定义树节点
typedef struct Node {
    int key;
    struct Node *left, *right;
} Node;

// 创建新节点
Node* newNode(int key)
{
    Node* node = (Node*)malloc(sizeof(Node));
    node->key = key;
    node->left = node->right = NULL;
    return node;
}

// 展平二叉树的递归函数
void flatten(Node* root)
{
    // 如果树为空或者是叶子节点，无需处理
    if (root == NULL || (root->left == NULL && root->right == NULL))
        return;

    // 如果存在左子树
    if (root->left != NULL) {
        // 先递归处理左子树，确保它是展平的
        flatten(root->left);

        // 保存原来的右子树指针
        Node* tmpRight = root->right;
        
        // 将左子树搬到右边
        root->right = root->left;
        root->left = NULL;

        // 找到当前右子链表（即原左子树）的末端
        Node* t = root->right;
        while (t->right != NULL) 
            t = t->right;
        
        // 将原右子树拼接到末端
        t->right = tmpRight;
    }

    // 继续递归处理当前的右子树
    flatten(root->right);
}

// 打印遍历结果
void inorder(Node* root)
{
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->key);
    inorder(root->right);
}

// 测试主函数
int main()
{
    /* 构建测试用例 2：
        1
       / \
      3   4
         /
        2
         \
          5
    */
    Node* root = newNode(1);
    root->left = newNode(3);
    root->right = newNode(4);
    root->right->left = newNode(2);
    root->right->left->right = newNode(5);

    flatten(root);

    printf("展平后的结果: ");
    inorder(root);
    // 预期输出: 1 3 4 2 5

    return 0;
}

深入解析与常见误区

在编写这段代码时，有几个细节需要特别注意，这些也是初学者最容易犯错的地方。

  • 寻找末尾节点的循环条件：

在代码中，我们看到 INLINECODE1bdab7d1。这里必须检查 INLINECODE4cfdec25，而不是 INLINECODEdd683a0a。因为在这个阶段，左子树已经被递归展平了，所有的 INLINECODE9c12b77e 指针都已经变成了 INLINECODE129379fe。如果我们去检查 INLINECODE46a74228，循环会立即终止，导致无法找到真正的链表尾部。

  • 递归的顺序：

为什么我们先处理左子树，而不是先处理右子树？

根据前序遍历的定义（根-左-右），左子树的所有节点必须排在右子树之前。如果我们先把右子树展平，一旦我们移动了左子树，就会覆盖掉 root->right，导致右子树丢失。因此，必须先保存或处理右子树，或者先移动并处理好左子树，再把右子树接上去。我们的解法属于后者：先展平左子树，把它移过来，找尾巴，把右子树接上去。

  • 空间复杂度的真相：

虽然我们没有使用队列、栈或数组，但这段代码并不是真正的 O(1) 空间复杂度。因为使用了递归，编译器会在幕后维护一个调用栈。在最坏的情况下（树退化为链表），递归深度可以达到 N，因此空间复杂度是 O(N)。

进阶思考：迭代与 Morris 遍历

如果你对性能有极致的追求，或者担心递归深度过大导致的栈溢出，你可以探索基于迭代的 Morris Traversal（莫里斯遍历）方法。

Morris 遍历的核心技巧在于利用空闲的指针（叶子节点的 INLINECODE4cb1e348 指针）来暂存回溯信息。在展平问题中，我们可以利用这一思想，找到当前节点左子树的最右节点（前驱节点），将其 INLINECODE9b22dd60 指向当前节点的右子树，然后直接将当前节点的右指针指向左子树。这样做可以省去递归栈，真正实现 O(1) 的空间复杂度，虽然代码逻辑会相对更晦涩一些，但它是面试中展示深厚功底的大杀器。

总结与实践建议

通过这篇文章，我们不仅解决了一个具体的算法问题，更重要的是学习了如何处理复杂的指针引用和树的结构变换。

关键点回顾：

  • 原地操作：通过巧妙地移动节点和拼接链表，避免了额外空间的使用。
  • 递归思维：将大问题分解为子问题（先展平子树），再合并结果（拼接）。
  • 指针细节：时刻注意不要在修改指针之前丢失对后续节点的引用（例如 tmpRight 的使用）。

给你的建议：

在理解这段代码时，不要只靠看。动手画图是学习树结构算法的最有效途径。拿出纸笔，画出一棵树，然后模拟代码的每一步，在图上画出指针的变化方向。当你能在脑海中清晰地模拟出节点移动的过程时，你就真正掌握了这个算法。

希望这篇深入的分析能帮助你更好地理解二叉树展平的问题。快去代码编辑器中尝试一下吧！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。如需转载，请注明文章出处豆丁博客和来源网址。https://shluqu.cn/51184.html
点赞
0.00 平均评分 (0% 分数) - 0 票

相关文章美国1G带宽/1T流量高速vps $17.99/年