Medium

题目描述

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

解题思路

解题思路

这道题要求将二叉树按照先序遍历的顺序展开为链表形式。有几种不同的解法：

方法一：递归（推荐）

核心思想是对每个节点，先递归处理左右子树，然后将左子树插入到当前节点和右子树之间。具体步骤：

  1. 递归处理左子树和右子树，使它们都变成链表
  2. 如果左子树存在，找到左子树链表的最后一个节点
  3. 将右子树连接到左子树链表的末尾
  4. 将左子树移到右子树的位置，左子树置空

方法二：迭代（Morris遍历思想）

利用类似Morris遍历的思想，对于每个节点，如果有左子树：

  1. 找到左子树的最右节点（即左子树的最后一个节点）
  2. 将当前节点的右子树连接到左子树最右节点的右子树
  3. 将左子树移到右边，左子树置空
  4. 继续处理下一个节点

方法三：先序遍历+重构

先进行先序遍历收集所有节点，然后重新构建链表结构。

方法一和方法二都能达到O(1)空间复杂度，其中方法一更容易理解，方法二更高效。

代码实现

class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root) return;
        
        flatten(root->left);
        flatten(root->right);
        
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        
        root->left = nullptr;
        root->right = left;
        
        TreeNode* curr = root;
        while (curr->right) {
            curr = curr->right;
        }
        curr->right = right;
    }
};

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        if not root:
            return
        
        self.flatten(root.left)
        self.flatten(root.right)
        
        left = root.left
        right = root.right
        
        root.left = None
        root.right = left
        
        curr = root
        while curr.right:
            curr = curr.right
        curr.right = right

public class Solution {
    public void Flatten(TreeNode root) {
        if (root == null) return;
        
        Flatten(root.left);
        Flatten(root.right);
        
        TreeNode left = root.left;
        TreeNode right = root.right;
        
        root.left = null;
        root.right = left;
        
        TreeNode curr = root;
        while (curr.right != null) {
            curr = curr.right;
        }
        curr.right = right;
    }
}

var flatten = function(root) {
    if (!root) return;
    
    flatten(root.left);
    flatten(root.right);
    
    const left = root.left;
    const right = root.right;
    
    root.left = null;
    root.right = left;
    
    let curr = root;
    while (curr.right) {
        curr = curr.right;
    }
    curr.right = right;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型递归解法迭代解法
时间复杂度O(n)O(n)
空间复杂度O(h)O(1)

注：n 为树中节点数量，h 为树的高度。递归解法的空间复杂度主要来自递归调用栈，最坏情况下为 O(n)。

相关题目