LC-2196 Medium LeetCode

2196. Create Binary Tree From Descriptions

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 82% Topics: Array, Hash Table, Tree, Binary Tree

Reading material

Arrays & Hashing 12 min Trees & Traversals 18 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

# tree
class Solution(object):
    def createBinaryTree(self, descriptions):
        """
        :type descriptions: List[List[int]]
        :rtype: Optional[TreeNode]
        """
        nodes = {}
        children = set()
        for p, c, l in descriptions:
            parent = nodes.setdefault(p, TreeNode(p))
            child = nodes.setdefault(c, TreeNode(c))
            if l:
                parent.left = child
            else:
                parent.right = child
            children.add(c)
        return nodes[next(p for p in nodes.iterkeys() if p not in children)]

Solution from kamyu104/LeetCode-Solutions · MIT