C++ 算法：将按顺序存储在数组中的二叉树转换为二叉链表

#include

struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };

void convertToLinkedList(TreeNode* root, TreeNode*& prev) { if (root == nullptr) { return; }

convertToLinkedList(root->left, prev);

// 将当前节点的左子树指向上一个节点
root->left = prev;
if (prev != nullptr) {
    prev->right = root;
}

prev = root;

convertToLinkedList(root->right, prev);

}

TreeNode* convertToLinkedList(TreeNode* root) { TreeNode* prev = nullptr; convertToLinkedList(root, prev);

// 找到链表的头节点
while (root != nullptr && root->left != nullptr) {
    root = root->left;
}

return root;

}

void printLinkedList(TreeNode* head) { while (head != nullptr) { std::cout << head->val << " "; head = head->right; } std::cout << std::endl; }

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

// 转换为链表
TreeNode* head = convertToLinkedList(root);

// 打印链表
printLinkedList(head);

return 0;

}

这个算法使用了中序遍历的思想，首先将左子树转换为链表形式，然后将当前节点连接到上一个节点的右侧，最后将右子树转换为链表形式。转换后，返回链表的头节点并打印链表的值。