问题描述
LeetCode 106. 从中序与后序遍历序列构造二叉树 (opens in a new tab)，难度中等。
给定两个整数数组 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]
提示:
1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000inorder和postorder都由 不同 的值组成postorder中每一个值都在inorder中inorder保证是树的中序遍历postorder保证是树的后序遍历
题解
corecode.Solution.java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
HashMap<Integer, Integer> map = new HashMap<>();
int[] inorder;
int[] postorder;
int postIndex;
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.inorder = inorder;
this.postorder = postorder;
for (int i = 0; i < inorder.length; ++i) {
map.put(inorder[i], i);
}
this.postIndex = postorder.length - 1;
return helper(0, postorder.length - 1);
}
public TreeNode helper(int inleft, int inright) {
if (inleft > inright) return null;
TreeNode root = new TreeNode(postorder[postIndex]); // 根节点
int index = map.get(postorder[postIndex]); // 用于拆分中序遍历
// inleft index inright
postIndex--;
// 必须先构建右子树，因为 postIndex 是递减的
// index + 1 x inright
root.right = helper(index + 1, inright);
// 再构建左子树
// inleft x index - 1
root.left = helper(inleft, index - 1);
return root;
}
}