Skip to content

Instantly share code, notes, and snippets.

@c02y
Created January 10, 2020 02:32
Show Gist options
  • Save c02y/820aec9440f795e323e96b3cab88233d to your computer and use it in GitHub Desktop.
Save c02y/820aec9440f795e323e96b3cab88233d to your computer and use it in GitHub Desktop.
reConstructBinaryTree
# https://cyc2018.github.io/CS-Notes/#/notes/7.%20%E9%87%8D%E5%BB%BA%E4%BA%8C%E5%8F%89%E6%A0%91
# https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=11157&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=cyc_github
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
result = []
class Solution:
def reConstructBinaryTree(self, pre, tin):
global result
if not pre or not tin:
return None
root = TreeNode(pre.pop(0))
index = tin.index(root.val)
root.left = self.reConstructBinaryTree(pre, tin[:index])
root.right = self.reConstructBinaryTree(pre, tin[index + 1:])
return result.insert(0, root.val)
def main():
pre = [1, 2, 4, 7, 3, 5, 6, 8]
tin = [4, 7, 2, 1, 5, 3, 8, 6]
tmp = Solution()
tmp.reConstructBinaryTree(pre, tin)
print(result)
if __name__ == '__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment