二叉树展开为单链表

问题分析

将一棵二叉树原地展开为一个单链表，链表节点顺序等于二叉树的先序遍历（根→左→右）。展开后每个节点的左指针必须为 null，右指针指向下一个节点。

解题思路

方法一（递归后序反向处理）：

• 使用递归函数返回当前子树展开后的“尾节点”。
• 对于当前节点 root：先递归展开右子树，得到 rightTail；再递归展开左子树，得到 leftTail。
• 如果左子树存在，将左子树链表插入到 root.right，原来的右子树接在 leftTail.right；并将 root.left 置空。

Leetcode 46.二叉树展开为链表-原题链接

题目内容

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

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

输入描述

一行二叉树的序列化数组$root$，节点值之间用空格隔开，空节点用null表示。

输出描述

层序遍历输出转化后的二叉树。末尾不保留多余的null。

样例1

输入

1 2 5 3 4 null 6

输出

1 null 2 null 3 null 4 null 5 null 6

样例2

输入

0

输出

0

提示

• 树中结点数在范围 $[0, 2000]$ 内
• $-100 <= Node.val <= 100$