Flatten Binary Tree to Linked List 要求"in place"

[non-static]

这个题目要求in-place，但目前的解好像都不是空间O(1)的。我有个O(1)空间的解想放上来但看到其他帖子里说这个repo是private了。现在可以pull request了么？

[soulmachine]

这题的要求是in place 的，那么空间肯定是O(1)的，我的代码也是空间O(1)的，所以你的说法目前的解好像都不是空间O(1)的是不对的。

你可以把代码贴上来，大家一起讨论讨论

[non-static]

现在的PDF里面三个解法都说自己是空间复杂度O(logn)。我的代码如下：

class Solution {
public:
    void flatten(TreeNode *root) {
        TreeNode *p = root;

        while (p != NULL)
        {
            if (p->left != NULL)
            {
                TreeNode *q = p->left;

                while (q->right != NULL)
                {
                    q = q->right;
                }

                q->right = p->right;
                p->right = p->left;
                p->left = NULL;
                p = p->right;
            }
            else if (p->right != NULL)
            {
                p = p->right;
            }
            else
            {
                return;
            }
        }
    }
};

[non-static]

有趣的是我优化了一下，变成了下面这样。提交后运行时间从上面那个代码的60ms变成了24ms。算法没有变化，只是少了一些if-else，居然快了一倍

class Solution {
public:
    void flatten(TreeNode *root) {
        while (root != NULL)
        {
            if (root->left != NULL)
            {
                TreeNode *q = root->left;

                while (q->right != NULL)
                {
                    q = q->right;
                }

                q->right = root->right;
                root->right = root->left;
                root->left = NULL;
            }

            root = root->right;
        }
    }
};

[soulmachine]

你这个算法，空间复杂度O(1)，但是时间复杂度是O(nlogn)，更慢了，只不过leetcode的数据集太小，看不出差别来

[non-static]

我知道的算法属于O(nlogn)的，但这属于用时间换空间，因为题目明确要求in-place。好像不可能做到O(n)时间O(1)空间吧。

[soulmachine]

做不到。目前就有两种，一种是我书里的，时间复杂度O(n)，空间复杂度O(logn)，第二种就是你这个，时间复杂度O(nlogn)，空间复杂度O(1) 。各有利弊。

[non-static]

嗯，我这里的意思是既然题目要求了in-place，这种空间O(1)的解法也应该被列到书里，你觉得呢？

[soulmachine]

恩，你这个解法很不错，空间做到了O(1)了，采纳了 :+1: