114 二叉树展开为链表

一、题目

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

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

二、题解

方法一：递归，反向先序遍历

思路：使用 DFS 递归。

正常先序遍历顺序是：

根 -> 左 -> 右

但是如果我们想原地修改指针，可以反过来处理：

右 -> 左 -> 根

用一个变量 prev 记录当前节点展开后右边应该连接的节点。

1. 核心思路

题目要求展开后的链表顺序和先序遍历一致：

根 -> 左 -> 右

如果从前往后处理，修改指针时容易丢失原来的左右子树。

所以可以反过来处理：

右 -> 左 -> 根

核心思想是：

  • 先递归处理右子树；
  • 再递归处理左子树；
  • 最后处理当前节点；
  • 用 prev 记录当前节点后面应该接的节点。

每处理一个节点时，让：

root.right = prev;
root.left = null;
prev = root;

这样就可以从后往前把整棵树串成链表。

2. 具体步骤

  1. 如果当前节点为 null，直接返回。
  2. 先递归展开右子树。
  3. 再递归展开左子树。
  4. 将当前节点的 right 指向 prev。
  5. 将当前节点的 left 置为 null。
  6. 更新 prev = root，表示当前节点成为新的链表头。

3. 关键逻辑

flatten(root.right);
flatten(root.left);

root.right = prev;
root.left = null;
prev = root;

解释：

  • 因为最终顺序是 根 -> 左 -> 右；
  • 所以反过来连接就是 右 -> 左 -> 根；
  • prev 表示当前节点后面应该连接的节点；
  • 每次将当前节点的 right 指向 prev；
  • 再将 left 置空，满足题目要求。

4. 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    // prev 表示当前节点展开后，右边应该连接的节点
    private TreeNode prev = null;

    public void flatten(TreeNode root) {
        // 1. 处理特殊情况
        if (root == null) {
            return;
        }

        // 2. 先处理右子树
        flatten(root.right);

        // 3. 再处理左子树
        flatten(root.left);

        // 4. 当前节点的 right 指向已经展开好的链表
        root.right = prev;

        // 5. 当前节点的 left 必须置空
        root.left = null;

        // 6. 更新 prev，当前节点成为新的链表头
        prev = root;
    }
}

5. 复杂度分析

时间复杂度：O(n)O(n)

说明：每个节点只会被访问一次，其中 n 是二叉树中的节点数量。

空间复杂度：O(h)O(h)

说明：递归调用栈的深度取决于树的高度，h 是二叉树的高度。最坏情况下，树退化成链表，空间复杂度为 O(n)O(n)。

方法二：原地修改，寻找左子树最右节点

思路：使用原地修改指针。

对于每一个节点 cur，如果它有左子树，那么按照先序遍历：

cur -> cur.left -> cur.right

所以应该把左子树移动到右边。

但是原来的右子树不能丢，需要把原来的右子树接到左子树的最右节点后面。

1. 核心思路

方法一使用递归，从后往前连接链表。

方法二不使用递归，而是不断调整当前节点的左右指针。

对于当前节点 cur：

  • 如果 cur.left == null，说明当前节点没有左子树，直接看下一个节点；
  • 如果 cur.left != null，就找到左子树中最右边的节点；
  • 把当前节点原来的右子树接到这个最右节点的 right 上；
  • 再把当前节点的左子树移动到右边；
  • 最后把当前节点的 left 置空。

这种方法的核心是：

  • 左子树应该排在右子树前面；
  • 原来的右子树不能丢；
  • 左子树的最右节点后面应该接原来的右子树。

2. 具体步骤

  1. 定义指针 cur，从根节点开始遍历。
  2. 如果 cur.left 不为空，找到 cur.left 这棵子树中的最右节点 pre。
  3. 将 cur.right 接到 pre.right 后面。
  4. 将 cur.left 移动到 cur.right。
  5. 将 cur.left 置为 null。
  6. 继续处理 cur.right。

3. 关键逻辑

TreeNode pre = cur.left;

while (pre.right != null) {
    pre = pre.right;
}

pre.right = cur.right;
cur.right = cur.left;
cur.left = null;

解释：

  • pre 是当前节点左子树中的最右节点；
  • 因为左子树展开后，最后一个节点后面应该接原来的右子树；
  • 所以执行 pre.right = cur.right；
  • 然后把左子树整体移动到右边；
  • 最后将 cur.left 置空。

4. 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        // 1. 定义当前遍历节点
        TreeNode cur = root;

        // 2. 从根节点开始，不断向右遍历
        while (cur != null) {

            // 3. 如果当前节点有左子树，需要调整指针
            if (cur.left != null) {

                // 找到左子树的最右节点
                TreeNode pre = cur.left;

                while (pre.right != null) {
                    pre = pre.right;
                }

                // 将当前节点原来的右子树接到左子树最右节点的后面
                pre.right = cur.right;

                // 将当前节点的左子树移动到右边
                cur.right = cur.left;

                // 当前节点的左指针置空
                cur.left = null;
            }

            // 4. 继续处理右边的节点
            cur = cur.right;
        }
    }
}

5. 复杂度分析

时间复杂度：O(n)O(n)

说明：每个节点最多被访问有限次，因此总时间复杂度为 O(n)O(n)。

空间复杂度：O(1)O(1)

说明：只使用了常数个额外指针变量，没有使用递归栈或额外数据结构。

评论