diff options
author | Jack Sangdahl <[email protected]> | 2024-07-14 19:11:51 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-07-14 19:11:51 -0600 |
commit | 2fc439bfc73fae4536d112e9a25d39c0bd0d0df1 (patch) | |
tree | 9faa739e4367e6f89c4222ee57ffa5d758961f70 /create_bt_from_desc.py | |
parent | 98b97129df2e0f284f9d9e5b13562e816855bd50 (diff) | |
download | leetcode-2fc439bfc73fae4536d112e9a25d39c0bd0d0df1.tar.gz leetcode-2fc439bfc73fae4536d112e9a25d39c0bd0d0df1.zip |
2196. create binary tree from descriptions
Diffstat (limited to 'create_bt_from_desc.py')
-rw-r--r-- | create_bt_from_desc.py | 54 |
1 files changed, 54 insertions, 0 deletions
diff --git a/create_bt_from_desc.py b/create_bt_from_desc.py new file mode 100644 index 0000000..001f540 --- /dev/null +++ b/create_bt_from_desc.py @@ -0,0 +1,54 @@ +# 2196. Create Binary Tree From Descriptions +from collections import defaultdict + +""" +you are given a 2d integer array 'descriptions' where 'descriptions[i] = +[parent_i, child_i, isleft_i]' indicates that 'parent_i' is the parent of +'child_i', in a binary tree of unique values. construct the binary tree +described by 'descriptions' and return its root. the test cases will be +generated such that the binary tree is valid. +""" + + +# Definition for a binary tree node. +class TreeNode(object): + def __init__(self, val=0, left=None, right=None): + self.val = val + self.left = left + self.right = right + + +class Solution(object): + def createBinaryTree(self, descriptions): + """ + :type descriptions: List[List[int]] + :rtype: Optional[TreeNode] + """ + children = set() + m = {} + for p, c, l in descriptions: + np = m.setdefault(p, TreeNode(p)) + nc = m.setdefault(c, TreeNode(c)) + if l: + np.left = nc + else: + np.right = nc + children.add(c) + root = (set(m) - set(children)).pop() + return m[root] + + +if __name__ == "__main__": + obj = Solution() + print( + obj.createBinaryTree( + descriptions=[ + [20, 15, 1], + [20, 17, 0], + [50, 20, 1], + [50, 80, 0], + [80, 19, 1], + ] + ) + ) + print(obj.createBinaryTree(descriptions=[[1, 2, 1], [2, 3, 0], [3, 4, 1]])) |