二叉树展开为链表

标签: 深度优先搜索 链表 二叉树

难度: 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) 额外空间)展开这棵树吗?

Submission

运行时间: 36 ms

内存: 15 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if root is None:
            return
        self.flatten(root.left)
        self.flatten(root.right)

        left = root.left
        right = root.right

        root.left = None
        root.right = left
        
        p = root
        while p.right:
            p = p.right
        p.right = right

Explain

该题解采用后序遍历的方式来展开二叉树为链表。具体思路如下: 1. 首先递归处理左子树,将左子树展开为链表。 2. 然后递归处理右子树,将右子树展开为链表。 3. 将原本的左子树作为根节点的右子树,原本的右子树拼接到当前右子树的末端。 4. 将根节点的左子树置为空。

时间复杂度: O(n)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if root is None:
            return
        
        # 递归处理左子树
        self.flatten(root.left)
        # 递归处理右子树
        self.flatten(root.right)

        # 暂存左右子树
        left = root.left
        right = root.right

        # 将左子树作为右子树
        root.left = None
        root.right = left
        
        # 将原来的右子树接到当前右子树的末端
        p = root
        while p.right:
            p = p.right
        p.right = right

Explore

使用后序遍历(先处理左子树,再处理右子树,最后处理根节点)可以便于我们在修改树结构时防止丢失对子树的引用。在先序或中序遍历中,如果先处理根节点,然后再展开子树,可能会因修改根节点的右子树指针而丢失原本的右子树引用。而在后序遍历中,由于子树已经被处理和展开,我们可以安全地修改根节点的指针,将处理好的左子树放置到右侧,然后再将原右子树接到新的右子树末端,这样可以有效地保持对所有节点的正确引用,避免数据丢失。

在执行题解的算法过程中,首先将左子树展开并置于根节点的右侧,这保证了根节点后是其左子树的所有节点(按照左子树的先序顺序)。然后,将原右子树拼接到现右子树的末端。由于整个操作开始于根节点后移向左子树,然后左子树的末尾连接到右子树,这自然形成了一个先序遍历的序列(根-左-右)。因此,整个链表自然保持了二叉树的先序遍历顺序。

在算法中,我们首先处理并展开左右子树,然后再进行节点的连接操作。在连接之前,我们已经将左右子树分别保存在变量中,这样即使根节点的左右指针被修改,也不会影响已经保存的树结构。因此,这种方式不会导致原树结构的破坏或数据丢失。实际上,这种方法恰恰是为了保证在修改指针时不丢失任何子树的数据。

确实,对于非常大的二叉树,递归可能导致栈溢出。可以使用迭代方法或显式栈来避免递归。例如,可以使用一个栈来模拟后序遍历的过程。首先将节点按先序遍历的顺序压入栈中(即先压右子节点,后压左子节点)。然后,依次从栈中取出节点,将节点的左子树设为null,右子树连接之前处理的节点。这样反向构建链表,从而不需要使用系统调用栈,减少了栈溢出的风险。