diff options
author | Jack Sangdahl <[email protected]> | 2025-02-21 22:52:44 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-02-21 22:52:44 -0700 |
commit | e2e526d3c6eed3cfded621c2180fb8d3d8817294 (patch) | |
tree | 4b6ae5b13f4c18e690fcfc7781444290de080f74 /recover_tree_preorder.py | |
parent | eb3697b5c7c80be7c0abf04524408f83cb4ed30d (diff) | |
download | leetcode-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.py | 41 |
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")) |