LC-0114 Medium LeetCode

114. Flatten Binary Tree to Linked List

Linked List Stack Tree Depth-First Search Binary Tree

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 68% Topics: Linked List, Stack, Tree, Depth-First Search, Binary Tree

Reading material

Linked Lists 14 min Stacks & Queues 11 min Trees & Traversals 18 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(h), h is height of binary tree

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    # @param root, a tree node
    # @return nothing, do it in place
    def flatten(self, root):
        self.flattenRecu(root, None)

    def flattenRecu(self, root, list_head):
        if root:
            list_head = self.flattenRecu(root.right, list_head)
            list_head = self.flattenRecu(root.left, list_head)
            root.right = list_head
            root.left = None
            return root
        else:
            return list_head

class Solution2(object):
    list_head = None
    # @param root, a tree node
    # @return nothing, do it in place
    def flatten(self, root):
        if root:
            self.flatten(root.right)
            self.flatten(root.left)
            root.right = self.list_head
            root.left = None
            self.list_head = root

Solution from kamyu104/LeetCode-Solutions · MIT