力扣第114题：二叉树展开为链表

力扣第114题：二叉树展开为链表

题目描述

给定一个二叉树，原地将其展开为一个单链表。

展开后的链表 应该满足以下条件：

1. 展开后的链表 只包含树的右子树。每个节点的左子树都应该为空。
2. 每个节点的右子树是其原来左子树的展开后的头节点。每个节点的左子树应该为空。

题目分析

这道题目实际上是要求我们将二叉树变成一个类似链表的结构，其中每个节点只有右子节点，且右子节点连接了原树中左子树的展开部分。该问题可以通过前序遍历来处理，因为我们要把当前节点展开，然后递归处理左子树和右子树。

解题思路

1. 前序遍历：我们可以通过前序遍历（根-左-右）来进行节点的转换。在遍历过程中，我们会遇到每个节点，首先处理当前节点，然后递归处理其左子树和右子树。
2. 变换过程：
   • 对于每个节点，首先保存右子树。
   • 将左子树设置为右子树。
   • 然后继续遍历原来的右子树（现在是左子树）。
3. 递归或迭代：我们可以选择递归或迭代方式来实现。递归方式更自然，但迭代方式不需要额外的栈空间。

代码实现

下面是 C 语言的递归实现：

#include <stdio.h>
#include <stdlib.h>

// 二叉树节点结构体
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 递归实现：将二叉树展开为链表
void flatten(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    
    // 如果当前节点有左子树，处理左子树
    if (root->left != NULL) {
        // 先保存右子树
        struct TreeNode* rightSubtree = root->right;
        
        // 将左子树变为右子树
        root->right = root->left;
        root->left = NULL;
        
        // 找到原来左子树的最右节点
        struct TreeNode* temp = root->right;
        while (temp->right != NULL) {
            temp = temp->right;
        }
        
        // 将保存的右子树连接到最右节点
        temp->right = rightSubtree;
    }
    
    // 递归处理右子树
    flatten(root->right);
}

// 辅助函数：创建树节点
struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

// 打印链表（右子树连接的形式）
void printFlattenedTree(struct TreeNode* root) {
    while (root != NULL) {
        printf("%d ", root->val);
        root = root->right;
    }
    printf("\n");
}

// 测试代码
int main() {
    // 构建测试二叉树
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(5);
    root->left->left = createNode(3);
    root->left->right = createNode(4);
    root->right->right = createNode(6);

    // 调用 flatten 函数将二叉树展开为链表
    flatten(root);

    // 打印展开后的链表
    printFlattenedTree(root);

    return 0;
}

代码解析

1. flatten 函数：这是主函数，接受一个根节点 root 作为输入，将其展开为链表。函数首先检查节点是否为空。如果节点有左子树，它将左子树移动到右子树的位置，并将左子树置为空。然后，函数递归处理右子树（新的右子树是左子树的原本右子树）。
2. 递归遍历：递归遍历是通过调用 flatten(root->right) 来继续处理原来的右子树。由于我们已经将左子树移到了右子树，所以不需要显式地遍历左子树。
3. createNode 函数：这是一个辅助函数，用来创建新的树节点。
4. printFlattenedTree 函数：该函数用于打印展开后的链表，因为展开后的链表是一个单链表，所有节点都只连接右子树。

时间复杂度与空间复杂度

• 时间复杂度：$O(n)$，其中 $n$ 是树的节点数。我们遍历了树中的每个节点一次，并且在每个节点上做常数时间的操作（如重指向右子树）。
• 空间复杂度：$O(h)$，其中 $h$ 是树的高度。递归调用的栈空间与树的高度成正比。对于平衡树，空间复杂度为 $O(\log n)$；对于完全不平衡的树，空间复杂度为 $O(n)$。

递归的前序遍历

递归处理时，我们可以通过前序遍历的方式，先处理根节点，再递归处理左子树和右子树。在展开二叉树时，我们对每个节点：

1. 将左子树移动到右子树位置。
2. 将原来的右子树连接到左子树的最右节点。

示例

假设输入的二叉树是：

        1
       / \
      2   5
     / \   \
    3   4   6

调用 flatten 后，树将被展开为：

1 - 2 - 3 - 4 - 5 - 6