114. 二叉树展开为链表(Medium)

题解

Python

# 循环实现
class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root: return 
        while root:
            if root.left:
                pre = root.left 
                while pre and pre.right:
                    pre = pre.right
                pre.right = root.right 
                root.right = root.left 
                root.left = None 
            else:
                root = root.right

# 递归实现
class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        def helper(root):
            if not root.left and not root.right: # 叶子节点
                return root 
            r = root.right
            if root.left:
                root.right = root.left 
                helper(root.left).right = r 
                root.left = None 
            return helper(root.right)
        
        if not root: return root
        helper(root)
        return root 

使用中序遍历，借助队列。原地变动并不限制空间复杂度为 O(1)。

class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        def preorder(root):
            if not root: return 
            queue.append(root)
            preorder(root.left)
            preorder(root.right)
        if not root: return root

        queue = []
        preorder(root)
        for i in range(len(queue) - 1):
            queue[i].right = queue[i + 1]
            queue[i].left = None