reConstructBinaryTree

reConstructBinaryTree.py

# 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()