| 68 | # self.right = None |
| 69 | |
| 70 | class Solution(object): |
| 71 | def constructFromPrePost(self, pre, post): |
| 72 | """ |
| 73 | :type pre: List[int] |
| 74 | :type post: List[int] |
| 75 | :rtype: TreeNode |
| 76 | """ |
| 77 | |
| 78 | def getLeftAndRight(pre, post): |
| 79 | # no more node. |
| 80 | if not pre: |
| 81 | return None |
| 82 | |
| 83 | # Get the index of the left root. |
| 84 | index = post.index(pre[0]) |
| 85 | |
| 86 | # post left tree |
| 87 | val_children = post[:index+1] |
| 88 | |
| 89 | # post right tree |
| 90 | val_brother = post[index+1:-1] |
| 91 | |
| 92 | # pre left tree |
| 93 | # Get the left tree pre list |
| 94 | # if left tree post list contains 3 elements |
| 95 | # then we will get equal in pre list. |
| 96 | t = len(val_children) |
| 97 | pre_val_children = pre[:t] |
| 98 | |
| 99 | # there is right tree. |
| 100 | # The elements are the rest of pre list. |
| 101 | pre_val_brother = pre[t:] |
| 102 | |
| 103 | left = pre[0] |
| 104 | |
| 105 | right = val_brother[-1] if val_brother else None |
| 106 | |
| 107 | # left, right, pre, post |
| 108 | return (left, right, pre_val_children, val_children, pre_val_brother, val_brother) |
| 109 | |
| 110 | def construct(root, pre, post): |
| 111 | x = getLeftAndRight(pre[1:], post) |
| 112 | if root and x: |
| 113 | if x[0] is not None: |
| 114 | root.left = TreeNode(x[0]) |
| 115 | if x[1] is not None: |
| 116 | root.right = TreeNode(x[1]) |
| 117 | |
| 118 | if root.left: |
| 119 | construct(root.left, x[2], x[3]) |
| 120 | |
| 121 | if root.right: |
| 122 | construct(root.right, x[4], x[5]) |
| 123 | |
| 124 | allRoot = TreeNode(pre[0]) |
| 125 | construct(allRoot, pre, post) |
| 126 | |
| 127 | return allRoot |
nothing calls this directly
no outgoing calls
no test coverage detected