第100道 LeetCode 热门题目：二叉树（第四部分）

目录

1 114. 二叉树展开为链表

2 105. 从前序与中序遍历序列构造二叉树

3 437. 路径总和 III

菜鸟做题（即将返校版），语言是 C++

1 114. 二叉树展开为链表

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

而先序遍历则是指依次访问左子树、随后访问右子树。

也就是说，在这种展开方式中，

其核心在于将左分支提前插入至右分支之前。

解题思路：通过递归的方法，在每个节点上首先将左子树连接到右子树的位置，并接着将右子树连接到左子树之后。

思路说明图：

我们关注的是节点"1"及其左右两侧的部分（分别用绿色和黄色标注）。具体来说，则需依次将左子树连接至节点"1"的右边位置，并将右子树安排在左边区域之后的位置）。同样的逻辑也适用于其他类似的情况如节点"2"等

 class Solution {

    
 public:
    
     void flatten(TreeNode* root) {
    
     if (!root) return;