如何将二叉查找树转移到递增顺序搜索？

Question

这是来自leetcode的问题。它说

给定二叉搜索树的根，按顺序重新排列树，使树中最左边的节点现在是树的根，每个节点没有左子节点，只有一个右子节点。

例2：，

我的代码几乎与下面相同，

void inorder(struct TreeNode *root, struct TreeNode **newRoot)
{
    if (root == NULL)
        return;

    inorder(root->left, newRoot);
    (*newRoot)->left = NULL;
    (*newRoot)->right = root;
    *newRoot = (*newRoot)->right;
    inorder(root->right, newRoot);
    return;
}

struct TreeNode* increasingBST(struct TreeNode *root)
{
    struct TreeNode *newRoot = calloc(1, sizeof(struct TreeNode));
    struct TreeNode *result = newRoot;
    inorder(root, &newRoot);
    //newRoot->left = NULL;
    //newRoot->right = NULL;
    return result->right;
}

在输入[2,1,4,null，null，3]之前，它可以很好地处理多个输入。实际上，它最终还是返回了，但我仍然收到了“超过时间限制”的错误。我发现有一个类似的解决方案，但它激活了上面的两行，

newRoot->left = NULL;
newRoot->right = NULL;

那就行了。我不明白为什么这两条线那么关键。请解释一下。

Answer 1

你发布的算法一个接一个地做两件事。

• 首先，它以有序的方式遍历树
• 其次，它将被访问的节点附加到当前节点的右侧节点，并使左侧节点禁用（将其赋值为空）

现在，下面的代码片段完成了树中最重要的部分：

newRoot->left = NULL;
newRoot->right = NULL;

它正在标记树的边界。首先，假设你没有标记你的边界（不使用上面的代码片段），你总是在树中，换句话说，你不是从树中出来的。

不过，我可以假设，您没有发布树的数据结构，在赋值时，left和right child没有设置为NULL。