114. 二叉树展开为链表

Posted on Edited on In Views: Word count in article: 807 Reading time ≈ 1 mins.

114. 二叉树展开为链表

题目链接：114. 二叉树展开为链表

题目描述

给你二叉树的根结点 root ，请你将它展开为一个单链表：

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

核心思考：保留原指针引用的先序遍历链接

根据题意，我们需要按照“先序遍历”（根 -> 左 -> 右）顺序串联二叉树节点，并将其改造为一棵只有右侧分支的变形树向后单调延展。

此题型易错的核心难点在于：在我们修改原本在树干中的树根父级引用下指向其原本的指针指向关系来延拓我们新增列链结构（将当前节点挂靠在 curr.right 时）后，如果原二叉树的左右从属枝叶关联没有被临时妥善保存起来，随即便会面临原生态挂载下子分支找寻不到被重写丢失悬空的内存风险。

解套方法：

  1. 优先备份：进入递归访问当前单元前刻不容缓地预保存该当次原有的二路指针引用即 left_node = node.left 以及 right_node = node.right 避免遗失覆膜打断关联。
  2. 开展串接操作：配合使用随同外界环境同步行进流转追踪更新位置进度节点标识量 curr（借助 nonlocal curr 修饰导入作用域权限）。重置清销剥离不合理的牵制挂留方向，使得 curr.left = None 且 curr.right = node，并随后推进让进度交棒给 curr = node。
  3. 安全继承递归推进：顺着原方案继续采用刚存下来隔离妥贴的预留数据指针引导往下对双方向分别延时打探下去铺设展开链。

解题思路 (Python)

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
# 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: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root:
            return
        curr = dummy = TreeNode()
        # 前序遍历接入链表
        def dfs(node):
            nonlocal curr
            
            if node == None:
                return

            left_node = node.left
            right_node = node.right

            curr.left = None
            curr.right = node
            curr = node

            dfs(left_node)
            dfs(right_node)

        dfs(root)
        return dummy.right

复杂度分析

  • 时间复杂度：$O(N)$。这里代表的 N 指向是总包含原二叉大主结构上的每个节点构成。我们借机按照单一线路顺次通过一回进行遍历探访。
  • 空间复杂度：$O(H)$，在最糟线状偏移极化的状态模型中可以最大逼退化致和树的高度即 $O(N)$ 深度比肩。这直接来源于程序底舱暗藏支撑深递归的回退推栈需求。