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]
【思路】
首先回忆一下如何根据两个顺序构造一个唯一的二叉树，就是以后续数组的最后一个元素作为切割点，先切分中序数组，根据中序数组，反过来切分后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。
说到一层一层切割，就应该使用递归来做。
- 第一步：如果数组大小为0的话，说明是空节点了
- 第二步：如果不为空，那么取后续数组最后一个元素作为节点元素
- 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
- 第四步：切割中序数组，切成中序左数组和中序右数组
- 第五步：切割后序数组，切成后序左数组和后序右数组
- 第六步：递归处理左区间和右区间
TreeNode traversal(int[] inorder, int[] postorder) { // 第一步 if (postorder.size() == 0) return null; // 第二步：后序遍历数组最后一个元素，就是当前的中间节点 int rootValue = postorder[postorder.size() - 1]; TreeNode root = new TreeNode(rootValue); // 叶子节点 if (postorder.size() == 1) return root; //第三步：找到切割点 int delimiterIndex; for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) { if (inorder[delimiterIndex] == rootValue) break; } // 第四步：切割中序数组，得到中序左数组和中序右数组 // 第五步：切割后序数组，得到后序左数组和后序右数组 //第六步 root.left = traversal(中序左数组，后序左数组); root.right = traversal(中序右数组，后序右数组); return root; }
综合版本
class Solution { Map<Integer, Integer> map; // 方便根据数值查找位置 public TreeNode buildTree(int[] inorder, int[] postorder) { map = new HashMap<>(); for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置 map.put(inorder[i], i); } return findNode(inorder, 0, inorder.length, postorder,0, postorder.length); // 前闭后开 } public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) { // 参数里的范围都是前闭后开 if (inBegin >= inEnd || postBegin >= postEnd) { // 不满足左闭右开，说明没有元素，返回空树 return null; } int rootIndex = map.get(postorder[postEnd - 1]); // 找到后序遍历的最后一个元素在中序遍历中的位置 TreeNode root = new TreeNode(inorder[rootIndex]); // 构造结点 int lenOfLeft = rootIndex - inBegin; // 保存中序左子树个数，用来确定后序数列的个数 root.left = findNode(inorder, inBegin, rootIndex, postorder, postBegin, postBegin + lenOfLeft); root.right = findNode(inorder, rootIndex + 1, inEnd, postorder, postBegin + lenOfLeft, postEnd - 1); return root; } }
class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { if(postorder.length == 0 || inorder.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 = postorderStart + (middleIndex - inorderStart); // 后序左子树的结束下标，需要通过中序得到的middleIndex的下标来辅助计算 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; } }
