LeetCode-106：从中序与后序遍历序列构造二叉树

题目描述：

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

思路分析：

因此根据上文所述，我们可以发现后序遍历的数组最后一个元素代表的即为根节点。知道这个性质后，我们可以利用已知的根节点信息在中序遍历的数组中找到根节点所在的下标，然后根据其将中序遍历的数组分成左右两部分，左边部分即左子树，右边部分为右子树，针对每个部分可以用同样的方法继续递归下去构造。

最后直接套上代码模板就行。最主要的是清楚根节点要做什么，然后递归左子树和右子树。

代码实现：

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     
    public TreeNode buildTree(int[] inorder, int[] postorder) {
     
    
   

    

     

    
    

     
        return build(inorder,0,inorder.length-1,
     
    
   

    

     

    
    

     

                          postorder,0,postorder.length-1);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

          TreeNode build(int[] inorder,int instart,int inend,
     
    
   

    

     

    
    

     
                    int[] postorder,int postart,int poend){
     
    
   

    

     

    
    

     
        if(instart>inend){
     
    
   

    

     

    
    

     
            return null;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        int index=0;
     
    
   

    

     

    
    

     
        int rootVal=postorder[poend];
     
    
   

    

     

    
    

     
        for(int i=instart;i<=inend;i++){
     
    
   

    

     

    
    

     
            if(rootVal==inorder[i]){
     
    
   

    

     

    
    

     

                      index=i;
     
    
   

    

     

    
    

     
                break;
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

              TreeNode root=new TreeNode(rootVal);
     
    
   

    

     

    
    

     
        int leftsize=index-instart;
     
    
   

    

     

    
    

     

              root.left=build(inorder,instart,index-1,
     
    
   

    

     

    
    

     

                              postorder,postart,postart+leftsize-1);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

              root.right=build(inorder,index+1,inend,
     
    
   

    

     

    
    

     

                              postorder,postart+leftsize,poend-1);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
        return root;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：小小谢先生，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/xiewenrui1996/article/details/113958559