leetcode114. 二叉树展开为链表 c语言

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};
 
int num; // 全局变量
// 前序遍历，将节点保存在数组中
void preorderTraversal(struct TreeNode* root, struct TreeNode*** res) {
    if (root != NULL) {
        num++;
        (*res) = (struct TreeNode**)realloc((*res), sizeof(struct TreeNode*) * num); 
// realloc更新申请内存的长度
        (*res)[num - 1] = root;  // 将节点保存到数组
        preorderTraversal(root->left, res);
        preorderTraversal(root->right, res);
    }
}
 
 
void flatten(struct TreeNode* root) {
    num = 0;
    struct TreeNode** res = (struct TreeNode**)malloc(0);
    preorderTraversal(root, &res);
    for (int i = 1; i < num; i++) { // 在循环中用指针修改节点的内容
        struct TreeNode *prev = res[i - 1], *curr = res[i];
        prev->left = NULL;
        prev->right = curr;
    }
    free(res);
}

以上方法是在先序遍历的函数前申请一个二维指针，入参为二维指针的地址。在先序遍历函数中给二维指针申请内存，内存大小是指针*节点个数。

或者另一种写法，先申请指针数组，再传入函数中保存指针。

 
struct TreeNode * TreeArray[2000];		//结点数组
int i;
 
void nodeToArray(struct TreeNode *root)		//把先序遍历的方法把结点存放到数组中
{
    if(root == NULL)
        return;
    TreeArray[i++] = root;
    nodeToArray(root->left);
    nodeToArray(root->right);
}
void flatten(struct TreeNode* root){
    memset(TreeArray,NULL,sizeof(TreeArray));		//先将数组中的值全部赋为NULL
    i=0;
    nodeToArray(root);
    int j=0;
    while(TreeArray[j] != NULL)				//将数组中的结点连接成单链表
    {
        TreeArray[j]->left = NULL;
        TreeArray[j]->right = TreeArray[j+1];
        j++;
    }
}