題目敘述

題目難度： Medium
題目敘述：給定一棵 Binary Tree 的 root，將 Binary tree 展平成一個 Linked List

Linked List 要與題目的 TreeNode 是相同的 class，right child pointer 要指向list中的下一個節點，而 left child pointer 皆指向null
Linked List 節點順序要與對這棵樹進行 Pre-order Traversal 的節點順序一樣

解法

一開始的想法

這題的想法沒有花很久時間，算是解到目前最快的一題，大概從有想法到AC大概20min

這題的目的是要將一棵任意的二元樹轉換為一個往右側節點生長的Linked List (其實就是 skewed tree)。我一開始的想法如下：

首先宣告一個指標，用來指向 right subTree 的 root，走到任意節點時，如果他的左子樹存在，就將其左子樹嫁接到當前節點的右子樹位置，但這樣原先的右子樹怎辦？這就是剛剛要宣告一個新指標的原因。接著嫁接完畢後就將原本 right subTree 的 root 接回來，接著持續在右子樹 traversal，一旦發現有節點具有 Left-child 則重複剛剛的步驟。

當然這個初始的想法後續再寫的過程中也有進行修改，成果如下：

我的解法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
       if(root == nullptr) return;
        TreeNode *current = root;
        TreeNode *ptr = nullptr;
        if(current->left!= nullptr){
            ptr = current -> right;
            current -> right = current -> left;
            current -> left = nullptr;

            while(current->right != nullptr){
                current = current -> right;
            }
            current -> right = ptr;
        }
    
        flatten(root->right);  
    }
};