JZ4 重建二叉树 python

JZ4 重建二叉树

考虑递归，注意前序遍历和后序遍历的序列在划分为子问题时，长度仍然保持相等

book method

错误记录

1. 未考虑输入为空的特殊情况

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, vin):
        if len(pre) != len(vin):
            return -1
        else:
            if pre: 
                Tree = TreeNode(pre[0])
                vin_idx = vin.index(pre[0])
                if vin_idx == 0:
                    Tree.left = None
                else:
                    Tree.left = self.reConstructBinaryTree(pre[1:1+vin_idx], vin[:vin_idx])
                if vin_idx == len(pre)-1:
                    Tree.right = None
                else:
                    Tree.right = self.reConstructBinaryTree(pre[vin_idx+1:], vin[vin_idx+1:len(vin)])
                return Tree
            return None