如何使用Python实现链表的二叉树展开为链表（Flatten Binary Tree to Linked List）

2023-04-11 00:00:00 链表如何使用展开

链表二叉树展开为链表的思路如下：

对于每一个节点，将其左子树插入到自身和右子树之间。
将该节点的指针移动到插入后的右子树末尾。
递归处理右子树，使其也按照同样的方式进行展开。

代码演示如下：

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
        self.flatten(root.left)
        self.flatten(root.right)
        # 将左子树插入到右子树之前
        if root.left:
            left_last = root.left
            while left_last.right:
                left_last = left_last.right
            left_last.right = root.right
            root.right = root.left
            root.left = None

使用字符串 "pidancode.com" 来演示如下：

相关文章