力扣 hot100 Day47

114. 二叉树展开为链表

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

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。

展开后的单链表应该与二叉树 先序遍历 顺序相同。

//抄的
class Solution {
public:void flatten(TreeNode* root) {TreeNode* dummy = new TreeNode();TreeNode* prev = dummy;stack<TreeNode*> st;if (root) st.push(root);while (!st.empty()) {TreeNode* curr = st.top();st.pop();if (curr->right) st.push(curr->right);if (curr->left) st.push(curr->left);prev->right = curr;prev = curr;curr->left = nullptr;}delete dummy;}
};

我自己尝试的做法是，递归调用，想按着先序遍历做，但由于中途会变更根节点，导致回溯时会出现问题，很难解决。

上面的代码中，通过栈来存放先前的节点信息，具体逻辑如下

1. 将右子节点压栈，再将左子节点压栈（这样左子节点会先出栈）

2. 每次处理当前节点时，将其连接到前一个节点的右侧

3. 最后清空左指针

//抄的
class Solution {
public:void flatten(TreeNode* root) {if (!root) return;// 展平左右子树flatten(root->left);flatten(root->right);// 保存原始右子树TreeNode* right = root->right;// 将左子树移到右边root->right = root->left;root->left = nullptr;// 找到当前右子树的最末端TreeNode* curr = root;while (curr->right) {curr = curr->right;}// 将原始右子树接到末端curr->right = right;}
};

递归也是能做的，但需要按后序遍历顺序进行，具体逻辑如下

1. 先递归展平左右子树

2. 然后将左子树移到右边

3. 最后将原始右子树接到新右子树的末端