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

题目：

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals pre and post are distinct positive integers.

Example 1:

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1] Output: [1,2,3,4,5,6,7]

Note:

1 <= pre.length == post.length <= 30

pre[] and post[] are both permutations of 1, 2, …, pre.length.

It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

解释：

# 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 constructFromPrePost(self, pre, post):        """        :type pre: List[int]        :type post: List[int]        :rtype: TreeNode        """        root_val=pre[0]        root=TreeNode(root_val)        if len(pre) == 1:            return root        index=post.index(pre[1])        pre_left,post_left=pre[1:index+2],post[:index+1]        pre_right,post_right=pre[index+2:],post[index+1:-1]                if pre_left:            root.left=self.constructFromPrePost(pre_left,post_left)        if pre_right:            root.right=self.constructFromPrePost(pre_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* constructFromPrePost(vector
   
    & pre, vector
    
     & post) {
           int root_val=pre[0];        TreeNode* root=new TreeNode(root_val);        if(pre.size()==1)            return root;        int idx=find(post.begin(),post.end(),pre[1])-post.begin();        vector
     
       pre_left(pre.begin()+1,pre.begin()+idx+2);        vector
      
        post_left(post.begin(),post.begin()+idx+1);        vector
       
         pre_right(pre.begin()+idx+2,pre.end());        vector
        
          post_right(post.begin()+idx+1,post.end()-1); if(pre_left.size()) root->left=constructFromPrePost(pre_left, post_left); if(pre_right.size()) root->right=constructFromPrePost(pre_right, post_right); return root; }};
        
       
      
     
    
   

总结：

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