🌳 114.二叉树展开为链表

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

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

思路

基本思想

为了实现将二叉树转换成一个前序遍历的链表,需要在遍历到一个节点的时候,将这个节点的右指针指向前序遍历的前一个节点,如果直接在前序遍历时将当前节点的右指针指向前一个节点,也就是根左右的遍历顺序时将右指针指向前一个节点,会导致右子树断链找不到的情况

所以在使用当前节点的右指针之前,需要确保当前节点的右子树已经被访问,三个遍历中没有一个遍历是这样的,所以需要改造遍历的方法

为了不让右子树断链,需要最开始就先访问右子树,又为了形成根左右这种前序遍历的链表结构,加上当前节点的左指针需要清空.需要形成右左根的遍历顺序,这样遍历到左节点时,右节点已经被访问过了,直接将使用右指针也不会出现问题,所以改造出了一个新的遍历方法

执行流程

1. 先遍历右节点
2. 再遍历左节点
3. 最后根节点需要将右指针指向当前节点的前一个节点,然后左指针清空
4. 再遍历右左根顺序的下一个节点时,需要记住上一个节点

代码

根据以上分析,得出以下代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    //形成自己的遍历顺序:右左根
    TreeNode *pre=nullptr;
    void flatten(TreeNode* root) {
        reinorder(root);
    }
    //逆前序遍历即可
    void reinorder(TreeNode* root){
        if(root==nullptr)
            return;
        //右左根的访问形式
        reinorder(root->right);
        reinorder(root->left);
        root->right=pre;
        root->left=nullptr;
        pre=root;
    }
};

总结

为了当前节点的右指针指向前序遍历中的前一个节点,并且左指针指向空,需要最先访问右节点,再访问左节点,最后访问根节点,形成右左根的访问顺序,相当于逆向的前序遍历,这样遍历到左的时候,左的右指针指向前一个节点,左指针清空就可以满足要求