剑指offer——04重建二叉树(Python3)

剑指offer——04重建二叉树(Python3)

思路:在数据结构中,有一个条件反射,谈及二叉树,就递归。所以在实现重建二叉树时,也应该用到递归的思想。

在前序遍历中,根节点处于第一个;在中序遍历中,根节点的左边为左子树节点,根节点右边为右子树节点。

根据性质构造根节点。

1、取出前序遍历的第一个节点作为根节点

2、在中序遍历中按照根节点分割左子树和右子树

3、递归

代码:

class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if len(pre) == 0:
            return None
        if len(pre) == 1:
            return TreeNode(pre[0])
        else:
            flag = TreeNode(pre[0])
            flag.left = self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1],tin[:tin.index(pre[0])])
            flag.right = self.reConstructBinaryTree(pre[tin.index(pre[0])+1:],tin[tin.index(pre[0])+1:] )
        return flag
上一篇:VBA在EXCEL中创建图形线条


下一篇:Socket 多线程FTP软件开发