本文主要是介绍【leetcode面试经典150题】75. 二叉树展开为链表（C++），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主，题解使用C++语言。（若有使用其他语言的同学也可了解题解思路，本质上语法内容一致）
【题目描述】
给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用
TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。 - 展开后的单链表应该与二叉树 先序遍历 顺序相同。
【示例一】
输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6]
【示例二】
输入：root = [] 输出：[]
【示例三】
输入：root = [0] 输出：[0]
【提示及数据范围】
- 树中结点数在范围
[0, 2000]内 -100 <= Node.val <= 100
【代码】
// 方法一：前序遍历class Solution {
public:void flatten(TreeNode* root) {vector<TreeNode*> l;preorderTraversal(root, l);int n = l.size();for (int i = 1; i < n; i++) {TreeNode *prev = l.at(i - 1), *curr = l.at(i);prev->left = nullptr;prev->right = curr;}}void preorderTraversal(TreeNode* root, vector<TreeNode*> &l) {if (root != NULL) {l.push_back(root);preorderTraversal(root->left, l);preorderTraversal(root->right, l);}}
};// 方法二：前序遍历和展开同步进行class Solution {
public:void flatten(TreeNode* root) {if (root == nullptr) {return;}auto stk = stack<TreeNode*>();stk.push(root);TreeNode *prev = nullptr;while (!stk.empty()) {TreeNode *curr = stk.top(); stk.pop();if (prev != nullptr) {prev->left = nullptr;prev->right = curr;}TreeNode *left = curr->left, *right = curr->right;if (right != nullptr) {stk.push(right);}if (left != nullptr) {stk.push(left);}prev = curr;}}
};// 方法三：寻找前驱节点class Solution {
public:void flatten(TreeNode* root) {TreeNode *curr = root;while (curr != nullptr) {if (curr->left != nullptr) {auto next = curr->left;auto predecessor = next;while (predecessor->right != nullptr) {predecessor = predecessor->right;}predecessor->right = curr->right;curr->left = nullptr;curr->right = next;}curr = curr->right;}}
};这篇关于【leetcode面试经典150题】75. 二叉树展开为链表（C++）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
