题目描述
给定一个二叉树，原地将它展开为一个单链表。
示例：
例如，给定二叉树 1 / 2 5 / \ 3 4 6将其展开为：1 2 3 4 5 6
题目链接：https://leetcode-/problems/flatten-binary-tree-to-linked-list/
思路1
从例子中可以看到，链表的链接顺序是树的先序遍历的顺序。所以，先先序遍历树，并将序列存到队列中，然后将节点出队列，更改节点的左指针为空，右指针为下一个节点即可。代码如下：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: void flatten(TreeNode* root) { if(root==nullptr) return; queue<TreeNode*> q; dfs(root, q); TreeNode* head = q.front(); q.pop(); TreeNode* cur = head; while(!q.empty()){ TreeNode* node = q.front(); q.pop(); cur->left = nullptr; cur->right = node; cur = node; } } void dfs(TreeNode* root, queue<TreeNode*>& q){ if(root==nullptr) return; q.push(root); dfs(root->left, q); dfs(root->right, q); }};时间复杂度：O(n)
空间复杂度：O(n)
思路2
使用先序遍历（中左右）的反序（右左中）遍历，然后再串联起来。
代码如下：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: void flatten(TreeNode* root) { if(root==nullptr) return; doFlatten(root); } TreeNode* pre= nullptr; void doFlatten(TreeNode* root){ if(root==nullptr) return; doFlatten(root->right); doFlatten(root->left); root->left = nullptr; root->right = pre; pre = root; }};时间复杂度：O(n)
空间复杂度：O(h)
参考
https://leetcode-/problems/flatten-binary-tree-to-linked-list/solution/dong-hua-yan-shi-si-chong-jie-fa-114-er-cha-shu-zh/
来源：/content-4-719051.html
如果觉得《【LeetCode-链表】二叉树展开为链表》对你有帮助，请点赞、收藏，并留下你的观点哦！
