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

题目链接链接: 从中序与后序遍历序列构造二叉树题目要求解题思路先在后序遍历数组中找到根节点根据中序遍历中找到根节点的位置在中序遍历中分割左子树和右子树再回到后序中找到左子树的后序遍历和右子树的后序遍历和从前序与中序遍历序列构造二叉树不同的是后序遍历的最后一个元素是根节点因此从后序的最后一个下标向前遍历从后向前遍历后序得到的顺序顺序是根 右 左也就是镜像的前序遍历此时就需要 先构建右子树再构建左子树即可代码实现classSolution{//记录 在后序中 遍历到到那个元素privateintindex0;privatestaticintfindPos(int[]arr,intval,intleft,intright){for(intposleft;posright;pos){if(arr[pos]val){returnpos;}}return-1;}publicTreeNodebuildTree(int[]inorder,int[]postorder){//每次使用需要重置 index 为末尾位置indexpostorder.length-1;returnbuildTreeHelper(inorder,postorder,0,inorder.length);}// left 和 right 为了在中序遍历中 分隔左子树和右子树的区间privateTreeNodebuildTreeHelper(int[]inorder,int[]postorder,intleft,intright){//如果是空区间 就说明是空树if(leftright){returnnull;}TreeNoderootnewTreeNode(postorder[index]);//指向前一个后序遍历元素index--;//在中序中找到当前根节点的位置intposfindPos(inorder,root.val,left,right);//[pos1, right) 是右子树区间root.rightbuildTreeHelper(inorder,postorder,pos1,right);//[left ,pos) 是左子树区间root.leftbuildTreeHelper(inorder,postorder,left,pos);returnroot;}}