美文网首页剑指offer-python
面试题7:重建二叉树

面试题7:重建二叉树

作者: fighting_css | 来源:发表于2018-06-18 17:11 被阅读0次

    【题目描述】
    输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
    【思路】
    前序遍历中第一个数为根节点,在中序遍历中寻找到根节点之后,可区分左右子树,便可递归构建左右子树
    注意边界条件判断
    1.若前序、中序为空,则二叉树为NULL
    2.递归时,若只剩一个节点,则该节点即为根节点,退出递归调用。
    【代码】

    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution:
        # 返回构造的TreeNode根节点
        def reConstructBinaryTree(self, pre, tin):
            # write code here
            def ConstructBinaryNode(pre,tin):
                tinlen = len(tin)
                rootvalue = pre[0]
                root = TreeNode(rootvalue)
                if tinlen==1:
                    return root
                
                #在中序遍历中寻找根节点
                leftlength = 0
                while leftlength<tinlen and tin[leftlength]!=rootvalue:
                    leftlength+=1
                #构建左子树
                if leftlength>0:
                    root.left = ConstructBinaryNode(pre[1:leftlength+1],tin[0:leftlength])
                #构建右子树
                if tinlen-leftlength>=2:
                    root.right = ConstructBinaryNode(pre[leftlength+1:],tin[leftlength+1:])
                return root
            prelen = len(pre)
            tinlen = len(tin)
            #树为空判断
            if prelen==0 or tinlen==0:
                return NULL
            return ConstructBinaryNode(pre,tin)
    

    相关文章

      网友评论

        本文标题:面试题7:重建二叉树

        本文链接:https://www.haomeiwen.com/subject/kivneftx.html