aboutsummaryrefslogtreecommitdiff
path: root/recover_tree_preorder.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-02-21 22:52:44 -0700
committerJack Sangdahl <[email protected]>2025-02-21 22:52:44 -0700
commite2e526d3c6eed3cfded621c2180fb8d3d8817294 (patch)
tree4b6ae5b13f4c18e690fcfc7781444290de080f74 /recover_tree_preorder.py
parenteb3697b5c7c80be7c0abf04524408f83cb4ed30d (diff)
downloadleetcode-e2e526d3c6eed3cfded621c2180fb8d3d8817294.tar.gz
leetcode-e2e526d3c6eed3cfded621c2180fb8d3d8817294.zip
1028. recover a tree from preorder traversal
Diffstat (limited to 'recover_tree_preorder.py')
-rw-r--r--recover_tree_preorder.py41
1 files changed, 41 insertions, 0 deletions
diff --git a/recover_tree_preorder.py b/recover_tree_preorder.py
new file mode 100644
index 0000000..bc87a66
--- /dev/null
+++ b/recover_tree_preorder.py
@@ -0,0 +1,41 @@
+# 1028. Recover a Tree From Preorder Traversal
+from leetcode import TreeNode
+from re import findall
+
+"""
+we run a preorder depth-first search (dfs) on the 'root' of a binary tree. at
+each node in this traversal, we output 'D' dashes (where 'D' is the depth of
+this node), then we output the value of this node. if the depth of a node is
+'D' the depth of its immediate child is 'D + 1'. the depth of the 'root' node
+is '0'. if a node has only one child, that child is guaranteed to be the left
+child. given the output 'traversal' of this traversal, recover the tree and
+return its root.
+"""
+
+
+class Solution(object):
+ def recoverFromPreorder(self, traversal):
+ """
+ :type traversal: str
+ :rtype: Optional[TreeNode]
+ """
+ nodes = [
+ (len(node[1]), int(node[2])) for node in findall("((-*)(\d+))", traversal)
+ ][::-1]
+
+ def recover(depth):
+ if not nodes or depth != nodes[-1][0]:
+ return None
+ node = TreeNode(nodes.pop()[1])
+ node.left = recover(depth + 1)
+ node.right = recover(depth + 1)
+ return node
+
+ return recover(0)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.recoverFromPreorder(traversal="1-2--3--4-5--6--7"))
+ print(obj.recoverFromPreorder(traversal="1-2--3---4-5--6---7"))
+ print(obj.recoverFromPreorder(traversal="1-401--349---90--88"))