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

跟着carl学算法，本系列博客仅做个人记录，建议大家都去看carl本人的博客，写的真的很好的！
代码随想录

LeetCode：106.从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
示例 2:
输入：inorder = [-1], postorder = [-1]
输出：[-1]

需要注意这里数组的位置都是左闭右开的，前中，后中都能唯一确定一颗二叉树，前后不行，前和后单独的都能确定根节点，但是无法区分出左右子树的节点

	public TreeNode buildTree(int[] inorder, int[] postorder) {if (inorder.length == 0 || postorder.length == 0)return null;return buildHelper(inorder, 0, inorder.length, postorder, 0, postorder.length);}private TreeNode buildHelper(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart,int postorderEnd) {if (postorderStart == postorderEnd)return null;int rootVal = postorder[postorderEnd - 1];TreeNode root = new TreeNode(rootVal);// 寻找根节点在中序数组中的位置int middleIndex;for (middleIndex = inorderStart; middleIndex < inorderEnd; middleIndex++) {if (inorder[middleIndex] == rootVal)break;}// 中序数组中 左中序的起始位置 和 右中序的起始位置int leftInorderStart = inorderStart;int leftInorderEnd = middleIndex;int rightInorderStart = middleIndex + 1;int rightInorderEnd = inorderEnd;// 后序数组中 左后序的起始位置 和 右后序的起始位置int leftPostOrderStart = postorderStart;int leftPostOrderEnd = leftPostOrderStart + (leftInorderEnd - leftInorderStart);int rightPostOrderStart = leftPostOrderEnd;int rightPostOrderEnd = postorderEnd - 1;root.left = buildHelper(inorder, leftInorderStart, leftInorderEnd, postorder, leftPostOrderStart,leftPostOrderEnd);root.right = buildHelper(inorder, rightInorderStart, rightInorderEnd, postorder, rightPostOrderStart,rightPostOrderEnd);return root;}