本文共 2207 字，大约阅读时间需要 7 分钟。

题目：

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 followingbinary tree:     3        / \      9  20     /  \        15   7

解释：

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def buildTree(self, preorder, inorder):        """        :type preorder: List[int]        :type inorder: List[int]        :rtype: TreeNode        """        #遍历中序，前序遍历的第一个结点一定是根节点，根节点后面紧跟的若干个结点一定是它的左子树        if not preorder:            return None        root_val=preorder[0]        index=inorder.index(root_val)        root=TreeNode(root_val)        pre_left,in_left=preorder[1:index+1],inorder[:index]        pre_right,in_right=preorder[index+1:],inorder[index+1:]        if pre_left:            root.left=self.buildTree(pre_left,in_left)        if pre_right:            root.right=self.buildTree(pre_right,in_right)        return root

c++代码：

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {
   public:    TreeNode* buildTree(vector
   
    & preorder, vector
    
     & inorder) {
           if (!preorder.size())            return NULL;        int root_val=preorder[0];        TreeNode* root=new TreeNode(root_val);        int idx=find(inorder.begin(),inorder.end(),root_val)-inorder.begin();        vector
     
      pre_left(preorder.begin()+1,preorder.begin()+idx+1);        vector
      
       in_left(inorder.begin(),inorder.begin()+idx);        vector
       
        pre_right(preorder.begin()+idx+1,preorder.end());        vector
        
         in_right(inorder.begin()+idx+1,inorder.end()); if(pre_left.size()) root->left=buildTree(pre_left,in_left); if(pre_right.size()) root->right=buildTree(pre_right,in_right); return root; }};
        
       
      
     
    
   

总结：

转载地址：http://hglcn.baihongyu.com/