力扣 LeetCode 106. 从中序与后序遍历序列构造二叉树（Day9：二叉树）

解题思路：

前中后序

给前中和后中都可以确定唯一的一棵二叉树

前中：先前 后中

中后：先中 后后

注意区间，统一左闭右开比较好

终止条件： if (postorderStart == postorderEnd) return null;

class Solution {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);}public TreeNode buildHelper(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd) {if (postorderStart == postorderEnd) return null;int rootValue = postorder[postorderEnd - 1];TreeNode root = new TreeNode(rootValue);int middleIndex = 0;for (middleIndex = 0; middleIndex < inorderEnd; middleIndex++) {if (inorder[middleIndex] == rootValue)break;}int leftInorderStart = inorderStart;int leftInorderEnd = middleIndex;int rightInorderStart = middleIndex + 1;int rightInorderEnd = inorderEnd;int leftPostorderStart = postorderStart;int leftPostorderEnd = postorderStart + (middleIndex - inorderStart);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;}
}