【算法分析与设计】二叉树展开为链表

? ? ? ?📝个人主页：五敷有你? ? ??
?🔥系列专栏：算法分析与设计
??稳中求进，晒太阳

题目

给你二叉树的根结点?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]

思想

方案一：二叉树的先序遍历(迭代)+集合

????????将二叉树展开为单链表之后，单链表中的节点顺序即为二叉树的前序遍历访问各节点的顺序。因此，可以对二叉树进行前序遍历，获得各节点被访问到的顺序。由于将二叉树展开为链表之后会破坏二叉树的结构，因此在前序遍历结束之后更新每个节点的左右子节点的信息，将二叉树展开为单链表。

方案二：递归

????????先展开右子树，再展开左子树，最后处理当前节点。通过维护一个 prev 节点，可以保证正确地连接每个节点。这种方式避免了使用额外的列表模拟栈

方案一

算法分析与设计

1. 迭代实现： 算法使用迭代的方式，通过一个循环遍历二叉树的每个节点。添加到集合中

2. 节点处理：?由于是先序访问，所以节点的顺序是没有问题的。然后拿出两个集合再做处理。

3. 移动指针： 移动指针到下一个节点，继续上述过程，直到所有节点都被处理。

代码实现

class Solution {
    public void flatten(TreeNode root) {
        TreeNode p = root;
        List<TreeNode> stack = new ArrayList<>();
        List<TreeNode> list1 = new ArrayList<>();
        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                stack.add(p);
                list1.add(p);
                p = p.left;
            }
            if (!stack.isEmpty()) {
                p = stack.remove(stack.size() - 1);
                p = p.right; // 更新p的值
            }
        }
        root = (list1.isEmpty()) ? null : list1.get(0);
        TreeNode last = (list1.isEmpty()) ? null : list1.get(0);
        TreeNode now = null;
        for (int i = 1; i < list1.size(); i++) {
            now = list1.get(i);
            last.right = now;
            last.left = null;
            last = now;
        }
    }
}

运行结果

?

方案二?

算法分析与设计

1. flatten 方法接收一个二叉树的根节点 root 作为输入参数。

2. 如果输入的根节点 root 为 null，直接返回，因为空树已经是展开的形式。

3. 对于非空树，递归地执行以下步骤：

   • 递归调用 flatten 方法处理右子树 root.right。
   • 递归调用 flatten 方法处理左子树 root.left。

4. 在递归回溯的过程中，对每个节点执行以下操作：

   • 将当前节点的右子树（已经被展开为链表的形式）连接到当前节点的左子树的最右边节点上。这一步骤确保了左子树被放置在右子树的前面。
   • 将当前节点的左子树置为 null，因为左子树已经被展开为右链表。

5. 更新 prev 指针为当前节点，以便在下一次递归回溯时正确连接右子树。

代码实现

class Solution {
    private TreeNode prev = null;

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

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

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

运行结果?