aboutsummaryrefslogtreecommitdiff
path: root/create_bt_from_desc.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-07-14 19:11:51 -0600
committerJack Sangdahl <[email protected]>2024-07-14 19:11:51 -0600
commit2fc439bfc73fae4536d112e9a25d39c0bd0d0df1 (patch)
tree9faa739e4367e6f89c4222ee57ffa5d758961f70 /create_bt_from_desc.py
parent98b97129df2e0f284f9d9e5b13562e816855bd50 (diff)
downloadleetcode-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.py54
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]]))