二叉树展开为链表

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

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

示例 1：

img

1
2
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

1
2
输入：root = []
输出：[]

示例 3：

1
2
输入：root = [0]
输出：[0]

提示：

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

进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

先序遍历的顺序是根 左 右，所以很显然操作方法是把左子树都插到右边来。

具体的步骤为：

  • 沿着右子树遍历二叉树
  • 如果当前节点有左子树，找到这棵左子树的最右边的节点。
  • 将左子树根节点一直到右子树的最右这条链插入当前节点后面
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public void flatten(TreeNode root) {
        while (root != null) {
            if (root.left != null) {
                TreeNode cur = root.left;
                while (cur.right != null) {
                    cur = cur.right;
                }
                cur.right = root.right;
                root.right = root.left;
                root.left = null;
            }
            root = root.right;
        }
    }
}