C语言算法-解答二叉树展开为链表算法问题的C语言实现

题目

给定一个二叉树，将其展开为一个单链表。展开后的单链表应该保持原二叉树的前序遍历顺序。

引言

在计算机科学中，对二叉树进行各种操作是非常常见的。一个常见的问题是将二叉树转换为链表。这个问题实际上是将二叉树进行前序遍历，然后将遍历结果按照顺序连接成链表。在这个问题中，我们将介绍一种递归的算法，它能够高效地将二叉树展开为链表。

算法思路

我们可以使用递归的方法来解决这个问题。具体的步骤如下：

1. 递归处理左右子树： 递归地将左子树和右子树展开为链表。
2. 连接左右子树： 将左子树展开后的链表接到根节点的右子树上，然后将根节点的右子树接到左子树展开后的链表的最右边节点上。

代码实现

// Definition for a binary tree node.
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void flatten(struct TreeNode* root) {
    if (!root) return;

    flatten(root->left);
    flatten(root->right);

    struct TreeNode* leftSubtree = root->left;
    struct TreeNode* rightSubtree = root->right;

    root->left = NULL;
    root->right = leftSubtree;

    struct TreeNode* current = root;
    while (current->right) {
        current = current->right;
    }

    current->right = rightSubtree;
}

算法分析

• 时间复杂度： 递归遍历了二叉树的所有节点，时间复杂度为O(n)，其中n为二叉树的节点数。
• 空间复杂度： 递归过程中使用了系统栈，空间复杂度为O(h)，其中h为二叉树的高度。

示例和测试

示例

考虑以下二叉树：

    1
   / \
  2   5
 / \   \
3   4   6

将其展开为链表后得到：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

测试

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

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void printList(struct TreeNode* node) {
    while (node) {
        printf("%d -> ", node->val);
        node = node->right;
    }
    printf("NULL\n");
}

int main() {
    // 创建二叉树
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->left->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->left->val = 3;
    root->left->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->right->val = 4;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->val = 5;
    root->right->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->right->val = 6;

    // 测试展开函数
    flatten(root);

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

    // 释放内存
    // (这里省略了释放内存的代码)

    return 0;
}

输出结果：

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

总结

本文介绍了一种递归的算法，用于将二叉树展开为链表。通过递归地处理左右子树，然后连接左右子树的展开后的链表，我们能够高效地解决这个问题。这种算法的时间复杂度为O(n)，空间复杂度为O(h)，在实际应用中具有很好的效果。