把二元樹展開成linked list，而且順序要跟preorder traversal一樣，三種traversal的模式我都知道，但每次preorder跟inorder就是會搞混，像這題我看圖片的時候，知道他要先找父節點再找左右子點，可以每次都把這個模式記成inorder@@

然後這題有提示說可以寫成O(1)的寫法

思路

看到回傳值是void的時候懞了，這樣是要用cout嗎？如果是cout的話，直接print preorder順序就好吧，但是對cout空陣列沒概念。

如果不是的話，我想到的應該是O(n)的解法，創建一個linked list的變數，然後Preorder traversal一遍樹，把巡到的值塞入list中，結束。

C++筆記

// 手動建立像這樣的變數與指標時，首先要先建立能抓著變數頭的指標`ans_root`，以及一個可以用來移動的指標`ptr`
TreeNode* ans_root = new TreeNode();
TreeNode* ptr = ans_root;

// 接著在每次需要新的Node時，用同樣的變數名建立新的Node跟新的指標`newptr`，把新的Node跟新建的變數連接在一起
TreeNode* newptr = new TreeNode();
newptr->val = curr->val;
ptr->right = newptr;
ptr = ptr->right;

程式碼

class Solution {
public:
    TreeNode* ans_root = new TreeNode();
    TreeNode* ptr = ans_root;
    void flatten(TreeNode* root) {
        preorder(root);
        root->val = ans_root->right->val;
        root->left = ans_root->right->left;
        root->right = ans_root->right->right;
    }
    
private:
    void preorder(TreeNode* curr) {
        if (curr == NULL)
            return;
        TreeNode* newptr = new TreeNode(curr->val);
        ptr->right = newptr;
        ptr = ptr->right;
        preorder(curr->left);
        preorder(curr->right);
    }
};

@@

遇到void的話，基本上就是把原本給的變數的內容改成答案。

本來想想一下O(1)解法，結果直接睡著，而且他說的O(1)是空間，不是時間

O(1)的解法，他這個應該是用postorder的方式，直接把原本的樹拆解。

參考：
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/discuss/1543611/C%2B%2B-easy-preorder-recursive-solution
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/discuss/1543162/C%2B%2B-Simple-Approach-using-Recursion-O(1)-space-complexity!