114. 二叉树展开为链表

1. 题目

给你二叉树的根结点 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) 额外空间）展开这棵树吗？

2. 思路

  • 已知题目要求将二叉树的所有结点按照先序遍历的顺序整合至二叉树节点的右节点，形成一条链表
  • 同时题目也要求了使用原地算法，即O(1)的额外空间来实现，因此不考虑通过先序遍历收集节点，随后遍历先序序列进行修改的方式
  • 进入flatten时，判断root是否为空，如果为空，则直接返回，因为题目提示中表示了树中节点范围是0-2000，即有可能root节点为空
  • 随后记录下当前root节点的左右子节点分别为变量left和right，记录下来的目的是防止后续的递归展开的过程中导致左右子节点的丢失
  • 构建TreeNode helper(TreeNode node, TreeNode preNode)方法，其node节点则为需要展开的节点，展开的方式其实就是preNode.right = node，但过程中需要注意的是需要将preNode.left置为空，helper方法的返回值则是展开后的上一个节点，后续的递归可接续插入至helper方法返回的节点当中
  • 展开完成后，递归处理node的左右子节点，并采用递归调用的方式，因为题目要求先序遍历，因此先处理根节点后，接续使用helper方法处理node.left和node.right节点
  • 当helper方法获取到的node节点为空时，直接返回preNode节点

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * 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) {
        if (root == null) {
            return;
        }

        var left = root.left;
        var right = root.right;
        helper(right, helper(left, root));
    }

    private TreeNode helper(TreeNode node, TreeNode preNode) {
        if (node == null) {
            return preNode;
        }

        preNode.right = node;
        preNode.left = null;
        var leftNode = node.left;
        var rightNode = node.right;

        return helper(rightNode, helper(leftNode, node));
    }
}

4. 复杂度

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

image-20231017100643296