Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6

递归算法

这种问题非常适合用递归做，每次完成一个节点的转换，剩下的事情都留给递归去做。这里需要处理的问题就是：需要将当前节点的右子树连接至左子树的前序遍历的最后一个节点的right指针。

我的C++代码实现如下：

void flatten(TreeNode *root) {
    if (!root) return;

    if (root->left) {
        TreeNode *pCurNode = root->left;
        if (root->right) {
            while (pCurNode->right) pCurNode = pCurNode->right;
            pCurNode->right = root->right;
        }
        root->right = root->left;
        root->left = nullptr;
    }

    flatten(root->right);
}

迭代算法

跟上面的非常相似，原理也相同，我的C++代码实现如下：

void flatten(TreeNode *root) {
    for (TreeNode *pCurChildRoot = root; pCurChildRoot != nullptr; pCurChildRoot = pCurChildRoot->right)
        if (pCurChildRoot->left) {
            TreeNode *pCurNode = pCurChildRoot->left;
            if (pCurChildRoot->right) {
                while (pCurNode->right) pCurNode = pCurNode->right;
                pCurNode->right = pCurChildRoot->right;
            }
            pCurChildRoot->right = pCurChildRoot->left;
            pCurChildRoot->left = nullptr;
        }
}

LeetCode[Tree]: Flatten Binary Tree to Linked List