Leetcode: 114. Flatten Binary Tree to Linked List | 含C++笔记

把二元树展开成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);
    }
};