You are given a 2D integer array descriptions
where descriptions[i] = [parenti, childi, isLefti]
indicates that parenti
is the parent of childi
in a binary tree of unique values. Furthermore,
- If
isLefti == 1
, thenchildi
is the left child ofparenti
. - If
isLefti == 0
, thenchildi
is the right child ofparenti
.
Construct the binary tree described by descriptions
and return its root.
The test cases will be generated such that the binary tree is valid.
Example 1:
Input: descriptions = [[20,15,1],[20,17,0],[50,20,1],[50,80,0],[80,19,1]]
Output: [50,20,80,15,17,19]
Explanation: The root node is the node with value 50 since it has no parent.
The resulting binary tree is shown in the diagram.
Example 2:
Input: descriptions = [[1,2,1],[2,3,0],[3,4,1]]
Output: [1,2,null,null,3,4]
Explanation: The root node is the node with value 1 since it has no parent.
The resulting binary tree is shown in the diagram.
Constraints:
-
1 <= descriptions.length <= 104
-
descriptions[i].length == 3
-
1 <= parenti, childi <= 105
-
0 <= isLefti <= 1
- The binary tree described by
descriptions
is valid.
SOLUTION:
# 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 makeTree(self, tree, node):
root = None
if node:
root = TreeNode(val = node)
if node in tree:
root.left = self.makeTree(tree, tree[node][0])
root.right = self.makeTree(tree, tree[node][1])
return root
def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:
roots = set(d[0] for d in descriptions)
tree = {}
for p, c, left in descriptions:
if p not in tree:
tree[p] = [None, None]
if left:
tree[p][0] = c
else:
tree[p][1] = c
if c in roots:
roots.remove(c)
root = list(roots)[0]
return self.makeTree(tree, root)
Top comments (0)