1俘陷、問題

給定一個二叉樹罗捎，將該二叉樹就地(in-place)轉換為單鏈表。單鏈表中節(jié)點順序為二叉樹前序遍歷順序岭洲。

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)
    {
        // 處理當前節(jié)點node盾剩，并將以當前節(jié)點為根節(jié)點的子樹
        // 拉直成鏈表雷激，更新last的值

        // 邊界條件
        if ( !node )
            return;

        // 當前節(jié)點為葉節(jié)點
        if ( !node->left && !node->right )
        {
            last = node;
            return;
        }

        // 如果當前節(jié)點不是葉節(jié)點，
        // 則當前節(jié)點要么node->left != nullptr
        // 要么node->right != nullptr
        // 要么node->left != nullptr && node->right != nullptr
        // 即至少有一個子樹

        // 將當前節(jié)點的左節(jié)點和右節(jié)點的地址存儲起來
        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是葉節(jié)點
            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;
}