#include <iostream>

using namespace std;

//二叉樹結構體
struct BinaryTreeNode
{
    explicit BinaryTreeNode(int value)
    :m_nValue(value)
    ,m_pLeft(nullptr)
    ,m_pRight(nullptr)
    {}
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};

void flatten(BinaryTreeNode* pRoot, BinaryTreeNode*& pLast)
{
    if(pRoot == nullptr) return;
    if(pRoot->m_pLeft == nullptr && pRoot->m_pRight == nullptr)
    {
        pLast = pRoot;
        return;
    }
    BinaryTreeNode* pLeft = pRoot->m_pLeft, *pRight = pRoot->m_pRight;
      
     //中
    pRoot->m_pLeft = nullptr;
    pRoot->m_pRight = pLeft;

      //左
    if(pLeft)
    {
        flatten(pLeft, pLast);
    }

       //右
    if(pRight)
    {
        if(pLast)
        {
            pLast->m_pRight = pRight;   
        }
        pLast = pRight;
        flatten(pRight, pLast);
    }
}

void pre_order(BinaryTreeNode* pRoot)
{
    if(pRoot == nullptr) return;
    cout << pRoot->m_nValue << " ";
    pre_order(pRoot->m_pLeft);
    pre_order(pRoot->m_pRight);
}

int main()
{
    BinaryTreeNode* pRoot = new BinaryTreeNode(1);
    pRoot->m_pLeft = new BinaryTreeNode(2);
    pRoot->m_pRight = new BinaryTreeNode(5);
    pRoot->m_pRight->m_pRight = new BinaryTreeNode(7);
    pRoot->m_pRight->m_pLeft = new BinaryTreeNode(6);
    pRoot->m_pLeft->m_pLeft = new BinaryTreeNode(3);
    pRoot->m_pLeft->m_pRight = new BinaryTreeNode(4);

    pre_order(pRoot);
    cout << endl;

    BinaryTreeNode* pNode = nullptr;
    flatten(pRoot, pNode);

    pre_order(pRoot);
    cout << endl;
}