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

题目：

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

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

For example, given

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

Return the following

binary 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, inorder, postorder):        """        :type inorder: List[int]        :type postorder: List[int]        :rtype: TreeNode        """        if not inorder:            return None        root_val=postorder[-1]        root=TreeNode(root_val)        index=inorder.index(root_val)        in_left,post_left=inorder[:index],postorder[:index]        in_right,post_right=inorder[index+1:],postorder[index:-1]        if in_left:            root.left=self.buildTree(in_left,post_left)        if in_right:            root.right=self.buildTree(in_right,post_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
   
    & inorder, vector
    
     & postorder) {
           if (!inorder.size())            return NULL;        int root_val=postorder[postorder.size()-1];        TreeNode* root=new TreeNode(root_val);        int idx=find(inorder.begin(),inorder.end(),root_val)-inorder.begin();        vector
     
      in_left(inorder.begin(),inorder.begin()+idx);        vector
      
       post_left(postorder.begin(),postorder.begin()+idx);        vector
       
        in_right(inorder.begin()+idx+1,inorder.end());        vector
        
         post_right(postorder.begin()+idx,postorder.end()-1); if(in_left.size()) root->left=buildTree(in_left,post_left); if(in_right.size()) root->right=buildTree(in_right,post_right); return root; }};
        
       
      
     
    
   

总结：

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