Leetcode 105. Construct Binary Tree from Preorder and Inorde

发布时间：2020-12-14 04:41:08 所属栏目：大数据来源：网络整理

导读：https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ Medium 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 ex

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

Medium

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,7]

Return the following binary tree:

    3
   /   9  20
    /     15   7

分治。先在前序里找到根结点，然后把中序分成左右子树分治。
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/34579/Python-short-recursive-solution.
5. Data Structures — Python 3.7.4 documentation
- https://docs.python.org/3/tutorial/datastructures.html?highlight=list%20pop#more-on-lists

 1 # Definition for a binary tree node.
 2 # class TreeNode:
 3 #     def __init__(self,x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 
 8 class Solution:
 9     def buildTree(self,preorder: List[int],inorder: List[int]) -> TreeNode:
10         idx = inorder.index( preorder.pop( 0 ) )
11         
12         node = TreeNode( inorder[ idx ] )
13         
14         node.left = buildTree( preorder,inorder[ 0:idx ] )
15         node.right = buildTree( preorder,inorder[ idx+1: ] )
16         
17         return node

View Python Code

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!