1、问题

给定一个二叉树，将该二叉树就地(in-place)转换为单链表。单链表中节点顺序为二叉树前序遍历顺序。

2、思路

3、代码

#include <iostream>

struct TreeNode
{
    // 多个成员
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode ( int x ) : val(x), left(nullptr), right(nullptr) {}
};

using namespace std;

class Solution
{
public:
    void flatten( TreeNode* root)
    {
        TreeNode* last = nullptr;  // 指向空指针
        preorder( root, last );
    }
private:
    void preorder( TreeNode* node, TreeNode* &last)
    {
        // 处理当前节点node，并将以当前节点为根节点的子树
        // 拉直成链表，更新last的值

        // 边界条件
        if ( !node )
            return;

        // 当前节点为叶节点
        if ( !node->left && !node->right )
        {
            last = node;
            return;
        }

        // 如果当前节点不是叶节点，
        // 则当前节点要么node->left != nullptr
        // 要么node->right != nullptr
        // 要么node->left != nullptr && node->right != nullptr
        // 即至少有一个子树

        // 将当前节点的左节点和右节点的地址存储起来
        TreeNode* left = node->left;
        TreeNode* right = node->right;
        TreeNode* left_last = nullptr;
        TreeNode* right_last = nullptr;

        if ( left )  // 左子树存在
        {
            // 将左子树拉直
            preorder( left, left_last );  // left 指针对应 left_last
            node->left = nullptr;
            node->right = left;
            last = left_last;  // 如果只有左子树的话，那么last就是left_last
        }
        if ( right )
        {
            // 将右子树拉直
            preorder( right, right_last );
            if ( left_last )
                left_last->right = right;  // left_last是叶节点
            last = right_last;
        }
    }
};

int main()
{
    TreeNode a(1);
    TreeNode b(2);
    TreeNode c(3);
    TreeNode d(4);
    TreeNode e(5);
    TreeNode f(6);

    a.left = &b;
    a.right = &e;
    b.left = &c;
    b.right = &d;
    e.right = &f;

    Solution S;
    S.flatten(&a);

    TreeNode* head = &a;
    while ( head )
    {
        if ( head ->left )
            cout << "Error!" << endl;
        cout << head->val << endl;
        head = head->right;
    }
    return 0;
}