来源：编程网事
大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位从字节跳到蔚来汽车的老哥从下面几点讲述了自己入职蔚来两个月的感受。
工作强度适中，上下班时间比较准时，自己的工作也得到了认可。
周末不加班，有了自己的时间，进行各种户外运动，身体状态变好了。
工作环境轻松愉快，有忙有闲，心情舒畅，睡眠显著改善，心理健康也提升了。
同事相处融洽，能和领导打成一片，氛围很好。
评论区也有在蔚来工作的脉友表示楼主所说的基本属实，这也引来一大批脉友的羡慕。不得不说这工作我也羡慕了。
言归正传，今天我们来分享一道蔚来汽车的面试原题「二叉树展开为链表」。
题目描述
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。
举个例子：
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
思路解析
我们可以使用先序遍历把所有节点保存到一个数组中，然后在依次把所有节点重新连接起来，这样会用到额外的数组保存节点，整个过程相当于遍历两遍二叉树中所有的节点。我们可以直接采用递归的方式，一边遍历二叉树一边对其展开，具体步骤如下：
展开二叉树的左子树。
展开二叉树的右子树。
把根节点，展开后的左子树和展开后的右子树重新连接在一起。
这就需要我们在递归函数中对指定的树展开的同时，并返回展开后的尾部节点，使得拼接操作更方便。
下面我们给出c++和python的两种代码实现。
c++代码
/**
* 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) {
dfs(root);
}
//展开根节点为root的子树，并返回展开链表的尾部节点
TreeNode* dfs(TreeNode* root) {
if (!root)
returnNULL;
//展开左子树
TreeNode* leftTail = dfs(root->left);
//展开右子树
TreeNode* rightTail = dfs(root->right);
//把展开的左右子树拼接在一起
if (leftTail) {
leftTail->right = root->right;
root->right = root->left;
root->left = NULL;
}
if (rightTail)
return rightTail;
elseif(leftTail)
return leftTail;
else
return root;
}
};
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def flatten(self, root: Optional[TreeNode]) -> None: """ Do not return anything, modify root in-place instead. """ self.dfs(root) # 展开根节点为root的子树，并返回展开链表的尾部节点 def dfs(self, root): ifnot root: returnNone # 展开左子树 left_tail = self.dfs(root.left) # 展开右子树 right_tail = self.dfs(root.right) # 把展开的左右子树拼接在一起 if left_tail: left_tail.right = root.right root.right = root.left root.left = None if right_tail: return right_tail elif left_tail: return left_tail else: return root
时间复杂度： 因为需要遍历二叉树中所有的节点，所以时间复杂度为O(n)，其中n为二叉树节点的总数。
空间复杂度： 整个过程使用了递归，会用到函数栈，所以空间复杂度跟二叉树的高度相关。
特别声明：以上内容仅代表作者本人的观点或立场，不代表新浪财经头条的观点或立场。如因作品内容、版权或其他问题需要与新浪财经头条联系的，请于上述内容发布后的30天内进行。
