二叉树转化为链表

约 1331 字大约 4 分钟

2024-10-17

⭐ 题目日期：

美团 - 2024/10/16

🧗难度系数：

⭐️ ⭐️ ⭐️ ⭐️

🌳 题目描述：

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

🌟 解题思路 1.0

递归解法：

！！！对递归比较陌生的朋友，请查阅

递归解二叉树的问题，基本都遵循以下三大要素：

当前节点需要从左右子树获得什么
拿到这些信息，当前层做点什么
返回什么给上一层

接下来，我们来一一回答这三个问题

当前节点需要从左右子树获得什么
以当前节点 root = 1 为例，当前节点需要左右子树转换成链表后的头节点和尾节点，2， 4， 5， 6，才能将左右链表以及自身组合成一个新的链表。2，5 其实是当前节点的左（root.left）右（root.right）节点，直接可以拿到，而 4， 6 需要通过左右子树拿到。所以，当前节点需要从左右子树获得各自转换成链表之后的尾节点。
拿到这些信息，当前层做点什么
根据题意，当前节点需要将左右子树转换成的链表组合成一个新的链表
- 将左子树设为空 root.left = null;
- 如果能拿到左子树的最后一个节点(leftLast)，说明左链表不为空
  root.right = left; leftLast.right = right；其中left, right 为当前节点的左右子树
- 如果不能拿到左子树的最后一个节点，说明左链表为空，
  root.right = right, 其中right 为当前节点的右子树
  当前层需要做的是将树状转换成链表
返回什么给上一层
这个问题在 1 讨论过，当前节点从左右子树拿的东西也是当前节点需要向上返回的。这也是递归的精髓所在，每一个节点做相同的事情。当前节点需要返回以当前节点为头节点的链表的尾节点给上一层。

代码

Java

public void flatten(TreeNode root) {
    flattenTreeToList(root);
}

private TreeNode flattenTreeToList(TreeNode root) {
    if (root == null) {
        return null;
    }

    // 控制左右子树，即控制左右链表的头节点，确保不管对当前的根节点做什么操作，都能找到左右子树
    TreeNode left = root.left;
    TreeNode right = root.right;

    // 找到左右子树展开为链表后的最后一个节点
    TreeNode lastLeft = flattenTreeToList(root.left);
    TreeNode lastRight = flattenTreeToList(root.right);

    // 根据题意，左子树设为空
    root.left = null;

    // 连接root，左子树的链表，右子树的链表
    if (lastLeft == null) {
        root.right = right;
    } else {
        root.right = left;
        lastLeft.right = right;
    }

    // 返回当前链表的最后一个节点给父节点
    if (lastRight == null) {
        return lastLeft == null ? root : lastLeft;
    }

    return lastRight;
}

题目链接

复杂度分析

时间复杂度：O(n), n 为树的节点数，每个节点都访问一遍

空间复杂度：O(h), 递归栈的调用空间, h 为树的高度

空间复杂度优化：

我们可以使用迭代的方式直接修改二叉树，不需要递归，从而避免递归栈空间的使用，将空间复杂度降到 O(1), 时间复杂度仍然为O(n), 所有节点最多访问两次。

从根节点开始，我们先调整大的框架。根节点 - 左子树 - 右子树，只需找到左子树的“最右”节点即可。至于左子树和右子树此时未必都是链表的形态。至此，我们再访问下一个节点，去调整子树的大的框架，完成之后，再顺着连接好的链表遍历去调整子子树的框架，最终将整颗树转化为链表。

Java

public void flatten(TreeNode root) {
    TreeNode cur = root;
    while (cur != null) {
        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;
        }
        cur = cur.right;
    }
}

🌟 解题思路 2.0

前序遍历解法

根据题意，展开后的链表与二叉树的先序遍历顺序相同。先序遍历一一拿到节点，前后相连。

！！！对前序遍历比较陌生的朋友，请查阅

代码

递归

Java

     private TreeNode pre = new TreeNode();

     public void flatten(TreeNode root) {
         flattenTreeToList(root);
         pre.right = null;
     }

     private void flattenTreeToList(TreeNode root) {
         if (root == null) {
             return;
         }
         TreeNode left = root.left;
         TreeNode right = root.right;
         pre.right = root;
         pre = root;
         flattenTreeToList(left);
         flattenTreeToList(right);
         root.left = null;
     }

复杂度分析

时间复杂度：O(n), n 为树的节点数，每个节点都访问一遍

空间复杂度：O(h), 递归栈的调用空间, h 为树的高度

迭代

Java

     public void flatten(TreeNode root) {
         if (root == null) {
             return;
         }

         Deque<TreeNode> stack = new LinkedList<>();
         stack.offerLast(root);
         TreeNode pre = null;

         while (!stack.isEmpty()) {
             TreeNode current = stack.pollLast();

             if (current.right != null) {
                 stack.offerLast(current.right);
                 current.right = null;
             }
             if (current.left != null) {
                 stack.offerLast(current.left);
                 current.left = null;
             }
             if (pre != null) {
                 pre.right = current;
             }
             pre = current;
         }
     }

复杂度分析

时间复杂度：O(n), n 为树的节点数，每个节点都访问一遍

空间复杂度：O(h), 栈的空间使用, h 为树的高度