75.二叉树展开为链表

题目

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

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

示例 1：

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

示例 2：

• 输入：root = []
• 输出：[]

示例 3：

• 输入：root = [0]
• 输出：[0]

提示：

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

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

思路

找左子树 [2,3,4] 的最右节点 → 4
把 4.right = 5（原来的右子树）
把 1.right = 2（原来的左子树）
把 1.left = null

结果：
1
 \
  2
 / \
3   4
     \
      5
       \
        6

继续遍历

找左子树 [3] 的最右节点 → 3
把 3.right = 4（原来的右子树）
把 2.right = 3
把 2.left = null

结果：
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

之后的节点都没有左子树，直接跳过，完成。

class Solution {
    fun flatten(root: TreeNode?): Unit {
        var curr = root

        while (curr != null) {
            // 如果当前节点有左子树，才需要处理
            if (curr.left != null) {
                // 第一步：找左子树的最右边节点
                var mostRight = curr.left
                while (mostRight?.right != null) {
                    mostRight = mostRight.right
                }

                // 第二步：把原来的右子树接到左子树最右节点的后面
                mostRight?.right = curr.right

                // 第三步：把左子树放到右边，左边清空
                curr.right = curr.left
                curr.left = null
            }

            // 处理完后，往右走，继续下一个节点
            curr = curr.right
        }
    }
}

复杂度

• 时间复杂度: 时间 O(n)：每个节点最多被访问两次（一次作为 curr，一次作为找最右节点时路过）

• 空间复杂度: 空间 O(1)：全程只用了几个指针，没有递归栈，没有额外数组

• 下一题

• 邮箱 ：charon.chui@gmail.com
• Good Luck!