114. 二叉树展开为链表

解析在1h40min处

震惊地发现了一个问题：
当结构体指针传递给函数时，会拷贝一份指针的值，但是函数内部的指针和函数外部的指针并不是指向同一个引用的，所以才会使得函数里面改变了，但是函数外部无变化，解决方案是在传参的时候，将结构体指针的引用传递过去
参考

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
  public:
    void flatten(TreeNode *root) {
        TreeNode *last = NULL;
        preorder(root, last);
    }

    void preorder(TreeNode *node, TreeNode *&last) {
        if (!node)
            return;
        if (!node->left && !node->right) {
            last = node;
            return;
        }

        TreeNode *left = node->left;
        TreeNode *right = node->right;
        TreeNode *left_last = NULL;
        TreeNode *right_last = NULL;
        if (left) {
            preorder(left, left_last);
            node->left = NULL;
            node->right = left;
            last = left_last;
        }
        if (right) {
            preorder(right, right_last);
            if (left_last) {
                left_last->right = right;
            }
            last = right_last;
        }
    }
};

void dfs(TreeNode *node) {
    if (!node) {
        return;
    }
    cout << node->val << " ";
    dfs(node->left);
    dfs(node->right);
}

int main() {
    TreeNode *a1 = new TreeNode(1);
    TreeNode *b1 = new TreeNode(2);
    TreeNode *b2 = new TreeNode(5);
    TreeNode *c1 = new TreeNode(3);
    TreeNode *c2 = new TreeNode(4);
    TreeNode *c3 = new TreeNode(6);

    a1->left = b1;
    a1->right = b2;
    b1->left = c1;
    b1->right = c2;
    b2->right = c3;

    Solution s;
    TreeNode *res = a1;
    s.flatten(a1);
    while (a1) {
        cout << a1->val << " ";
        a1 = a1->right;
    }

    return 0;
}