将二叉树展平成链表

引言

二叉树中的每个节点最多有两个子节点，即左子节点和右子节点，这使其成为一种分层数据结构。为了将二叉树转换为链表，必须以特定顺序重新排列树节点以形成线性结构。此过程称为“扁平化”。目标是重新排列二叉树的节点，使其树结构保持不变，同时创建链表。重要的是要以特定顺序创建链表，以方便简单的遍历。

方法 1：递归

递归方法采用深度优先遍历方式，通过迭代遍历树结构将二叉树扁平化为链表。该函数在每个阶段寻找一个基本情况，确保在检测到空节点时停止。该方法在扁平化左子树之前保留对右子树的引用，这对于后续的重新连接至关重要。然后通过对左子树的递归调用重复该过程。该函数扁平化左子树，然后通过调整指针将其移动到当前节点的右侧。它递归地扁平化原始右子树，并继续到这个新的扁平化右子树的末尾。由于它是递归的，整个二叉树都被检查，并且节点以特定序列重新排列以创建链表。递归之所以优雅，是因为它可以将复杂问题分解为更小、更易于管理的小问题，从而产生更简洁、更具表达力的代码。

代码

输出

代码解释

二叉树节点定义

• 概述了二叉树节点的结构，该结构由三个元素组成：指向左右子节点的指针（left 和 right）和一个整数值（val）。

扁平化函数

• 主要用于将二叉树转换为链表。
• 接受指向二叉树根节点的指针作为输入。

基本情况验证

• 如果当前节点 (root) 为 NULL，则函数返回并作为递归的基本情况。通过这样做，确保递归在每个分支的末尾结束。

保存右子树

• 保留对当前节点的右子树 (root->right) 的引用。这需要稍后重新连接。

左侧扁平化子树

• 要扁平化当前节点的左子树，请在其自身上递归使用 flatten(root->left)。

将扁平化左子树转移到右侧

• 扁平化的左子树被移动 (root->right = root->left) 到当前节点的右侧。
• 为了保持链表结构完整，将左子节点设置为 NULL。

向右前进，直到扁平化子树的末尾

• 使用 while 循环迭代地前进到扁平化子树的右端。

原始右子树扁平化

• 原始右子树通过递归使用 flatten(rightSubtree)) 进行扁平化。

将末尾与扁平化右子树连接

• (root -> right = rightSubtree) 将扁平化右子树连接到当前节点的末尾。

打印链表函数

• 定义 printList 函数，该函数打印扁平化链表的值。
• 接受指向链表头节点的指针作为输入。

方法 2：堆栈

此方法使用显式堆栈来跟踪节点，因为它遍历图。根节点被压入算法已初始化的空堆栈中。在 while 循环的每次迭代中，从堆栈中移除一个节点，该循环一直运行直到堆栈为空。如果存在堆栈，则首先将右子节点压入堆栈，然后压入左子节点。由于这种安排，左子节点的处理先进行。该技术同时修改指针以将当前节点连接到适当的子节点。二叉树通过使用堆栈显式管理遍历顺序并相应地修改指针进行深度优先扁平化。当不希望进行递归时，此方法特别有用，因为显式堆栈提供了一种有组织的方法来顺序处理遍历和扁平化过程。

代码

输出

代码解释

二叉树节点定义

• 概述了二叉树节点的结构，该结构由三个元素组成：指向左右子节点的指针（left 和 right）和一个整数值（val）。

堆栈节点定义

• 描述了堆栈节点的结构，该结构具有指向下一个堆栈节点 (next) 的指针和指向树节点 (node) 的指针。

堆栈定义

• 定义了一个单组件堆栈结构，它是指向堆栈顶部 (top) 的指针。

堆栈初始化

• 通过为堆栈结构分配内存并将顶部指针设置为 NULL，createStack() 初始化一个空堆栈。

空堆栈检查

• 在确定堆栈是否为空时，isEmpty() 检查顶部指针是否为 NULL。

压入机制

• 使用 push() 将新节点添加到堆栈。它创建一个新的堆栈节点，为其分配内存，将其节点设置为给定的树节点，并相应地修改顶部指针。

弹出函数

• pop() 从堆栈中取出顶部节点并返回它。它释放堆栈节点的内存，获取顶部节点的树节点，检查空堆栈，并修改顶部指针。

扁平化机制

• 主要函数 flatten() 使用基于迭代堆栈的方法将二叉树的根扁平化为链表。
• 在初始化空堆栈并添加根节点后，它会在修改指针的同时迭代处理节点。

方法 3：无堆栈迭代

此技术使用线程二叉树架构隐式模拟堆栈的功能。它利用了 Morris 遍历树遍历方法，该方法将每个节点的最右侧子节点与其在中序遍历序列中的后继节点连接起来，从而改变树拓扑。Morris 遍历经过修改以实现扁平化目的，以便它可以同时遍历和扁平化树，从而消除了对堆栈或其他额外数据结构的需求。该算法通过在节点之间创建线程连接并沿途修改指针，快速准确地遍历树。此技术的特点是其恒定的空间复杂度，这使其成为递归和基于堆栈的方法的省内存且有效的替代方案。

代码

输出

代码解释

二叉树节点定义

• 概述了二叉树节点的结构，该结构由三个元素组成：指向左右子节点的指针（left 和 right）和一个整数值（val）。

扁平化函数

• 通过使用线程树遍历方法 Morris 遍历，flatten 函数会就地更改二叉树。
• 该技术为每个具有左子节点的节点搜索左子树中最右侧的节点。此过程遍历树节点。
• 然后将左子树附加到当前节点的右侧，并通过将右子树移动到最右侧节点的右侧来形成线程连接。
• 当前节点的左子节点被赋值为 NULL。

主函数

• 在主函数中构建一个示例二叉树。
• 为了使用 Morris 遍历扁平化二叉树，调用 flatten 函数。
• 遍历扁平化链表会产生原始二叉树的线性化结构。

内存解除分配

主函数中的 while 循环释放为扁平化链表和二叉树节点分配的内存。链表中的每个节点在遍历时都会被释放。