树问题中的递归函数

Question

我有这个功能可以将二叉树转换为链表。由于 flatten_helper 函数 returns void，我无法理解这里的递归是如何工作的。那么当递归函数 returns 无效时实际发生了什么？有人可以帮我理解这里的代码发生了什么吗？

此外，任何理解树问题中递归的链接都将受到高度赞赏，因为我正在努力掌握这些类型的问题。

void flatten_helper(struct TreeNode* root, struct TreeNode** prev)
{
    if (root == NULL) return;
    flatten_helper(root->right, prev);
    flatten_helper(root->left,  prev);    
    root->right = *prev;
    root->left = NULL;
    *prev = root;    
}
void flatten(struct TreeNode* root)
{
    struct TreeNode **prev; 
    prev = (struct TreeNode *)malloc(sizeof(struct TreeNode *));   
    *prev = NULL;
    flatten_helper(root, prev); 
    *prev = NULL;
    free(prev);
 }

代码学分 - Leetcode

Answer 1

不要将 flatten_helper() 视为函数，而应将其视为过程。它没有 return 一个值，它实际上做了一些工作（它将 root->right 设置为 *prev，root->left 为 NULL，*prev 为 root）。