Leetcode106.从中序与后序遍历序列构造二叉树

看到二叉树的遍历就首先想到递归。

• 第一步：如果数组大小为零的话，说明是空节点了。

• 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。

• 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点

• 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）

• 第五步：切割后序数组，切成后序左数组和后序右数组

• 第六步：递归处理左区间和右区间

  class Solution {
      public TreeNode buildTree(int[] inorder, int[] postorder) {
          if(inorder.length==0 || postorder.length==0) return null;
          return traversal(inorder,postorder);
      }
      public TreeNode traversal(int[] inorder,int[] postorder){
          if(postorder.length==0) return null;
          TreeNode root=new TreeNode(postorder[postorder.length-1]);
          if(postorder.length==1) return root;
  
          int index;
          for(index=0;index<inorder.length;index++){
              if(inorder[index]==postorder[postorder.length-1]) break;
          }
          int[] leftInorder=Arrays.copyOfRange(inorder,0,index);
          int[] rightInorder=Arrays.copyOfRange(inorder,index+1,inorder.length);
          int[] leftPostorder=Arrays.copyOfRange(postorder,0,leftInorder.length);
          int[] rightPostorder=Arrays.copyOfRange(postorder,leftInorder.length,postorder.length-1);
          root.left=traversal(leftInorder,leftPostorder);
          root.right=traversal(rightInorder,rightPostorder);
          return root;
      }
  }