114. 二叉树展开为链表

问题描述

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

分析

注意，这里应该使用同样的TreeNode，也就是评判时，直接看原始结点的值，不能用new TreeNode然后自己赋值。

代码（非原地）

class Solution {
public:
    vector<TreeNode*> v;
    void solve(TreeNode* root) {
        if (root == nullptr) {
            return ;
        }
        v.push_back(root);
        solve(root->left);
        solve(root->right);
    }
    void flatten(TreeNode* root) {
        solve(root);
        TreeNode* p = new TreeNode();
        for (int i = 0; i < v.size(); i++) {
            p->right = v[i];
            p->left = nullptr;
            p = p->right;
        }
    }
};

此外，关于new，会变化原始指针的位置：

typedef struct A {
    int val = 0;
    A* next;
}A;
int main()
{
    A* a;
    A* p = a->next;
    p = new A();
    p->val = 555;
    printf("%d \n", a->next->val);
    // 输出为0，可知此时的p并不是a->next;
}