二叉树展开为链表

LeetCode 114 · Medium · 1 min · 榎aaaa

因为要求O(1)的空间复杂度，因此不能再使用额外的容器，所以这里使用了一个原地算法

思路如下：最终结果是将原来的树退化为了一条沿着右子树不断延伸的链表，根据结果不难发现：越是靠右的节点，在链表中的位置越靠前；而越是靠左的节点，在链表中的位置越往后

因此，可以通过迭代，每次将父节点的整棵左子树插入父节点与右子树之间

具体实现：

先确定迭代终止条件：当前节点为空

之后判断当前节点是否存在左节点（因为需要做的就是将左子树插入），如果左子树不存在，就可以认为此时位于最左边的节点，也就是此时这一支已经满足了单链表要求；然后就可以对右子树进行遍历，当到达右子树最后一个结点之后，就把父节点的整颗右子树挂在当前节点的右枝，再将根节点的左子树完整的移动到右子树，左子树置空即可

 1void flatten(TreeNode* root)
 2{
 3    while(root)
 4    {
 5        if(root->left)
 6        {
 7            auto temp = root->left;
 8            while(temp->right) temp = temp->right;
 9            temp->right = root->right;
10            root->right = root->left;
11            root->left = nullptr;
12        }
13        root = root->right;
14    }
15}