美文网首页
[Tree]105. Construct Binary Tree

[Tree]105. Construct Binary Tree

作者: 野生小熊猫 | 来源:发表于2019-02-23 02:33 被阅读0次
    • 分类:Tree
    • 时间复杂度: O(n) 这种把树的节点都遍历一遍的情况时间复杂度为O(n)
    • 空间复杂度: O(h) 树的节点的深度

    105. Construct Binary Tree from Preorder and Inorder Traversal

    Given preorder and inorder traversal of a tree, construct the binary tree.

    Note:
    You may assume that duplicates do not exist in the tree.

    For example, given

    preorder = [3,9,20,15,7]
    inorder = [9,3,15,20,7]
    

    Return the following binary tree:

        3
       / \
      9  20
        /  \
       15   7
    

    代码:

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def buildTree(self, preorder: 'List[int]', inorder: 'List[int]') -> 'TreeNode':
            
            if preorder==None or inorder==None or len(preorder)!=len(inorder):
                return None
            return self.helper(preorder,inorder,0,0,len(inorder)-1)
        
        def helper(self,preorder,inorder,pre_st,in_st,in_ed):
            if pre_st>=len(preorder) or in_st>in_ed:
                return
            root=TreeNode(preorder[pre_st])
            for i in range(in_st,in_ed+1):
                if inorder[i]==preorder[pre_st]:
                    break
            root.left=self.helper(preorder,inorder,pre_st+1,in_st,i-1)
            root.right=self.helper(preorder,inorder,pre_st+(i-in_st)+1,i+1,in_ed)
            return root
    

    讨论:

    1.考察前序遍历和中序遍历的特点,利用递归/分治来解这道题
    2.注意几个位置,一个pre_st,一个in_st,in_ed

    相关文章

      网友评论

          本文标题:[Tree]105. Construct Binary Tree

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