114. 二叉树展开为链表 - 力扣(LeetCode)

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

一解

使用 dfs,递归的把左子树转换为右子树,并将原来右子树放其后面。

# 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 not root: return
        right_child = self.flatten(root.right)
				# 把整理好的左子树根节点放到 root 的右子树,记为 l1
        root.right = self.flatten(root.left)
        root.left = None
				# 若 l1 为空,则将右子树直接接上
        if not root.right:
            root.right = right_child
				# 若 l1 不为空,找最 l1 的最边节点
        else:
            node = root.right
            while node.right:
                node = node.right
            node.right = right_child
        return root
  • 时间复杂度 O(n):n 为树的高度,最坏情况,该树只有左子树。
  • 空间复杂度 O(n):n 为树的高度,最坏情况,该树只有左子树,需要递归到最左结点。

二解

使用迭代法,设当前结点为 cur:

  1. 若 cur 存在左子结点:
    1. 将 cur 的右结点作为 cur 的「第一个左子结点下的最右结点的右孩子」。
    2. 将 cur 的第一个左子结点放到 cur 的右子结点(左子树 l1 变为右子树,cur.right 会继续处理 l1)。
    3. 将 cur 左子结点置空。
  2. 令 cur 指向右孩子。
  3. 重复上述过程。

将 predecessor 和 nxt

class Solution:
    def flatten(self, root: TreeNode) -> None:
        curr = root
        while curr:
            if curr.left:
                predecessor = nxt = curr.left
                while predecessor.right:
                    predecessor = predecessor.right
                predecessor.right = curr.right
                curr.left = None
                curr.right = nxt
            curr = curr.right
  • 时间复杂度 O(n):n 为结点数量。
  • 空间复杂度 O(1)。
关闭