106. 从中序与后序遍历序列构造二叉树
题目描述
输入两个整数数组：inorder 是某棵二叉树的中序遍历结果，postorder 是同一棵树的后序遍历结果。
树中所有节点值互不相同。根据这两个序列重建这棵二叉树，并返回根节点。
返回的树按层序数组表示，null 代表空位。
示例 1
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] 输出：[3,9,20,null,null,15,7]
解释：后序最后一个值 3 是根；中序里 3 左侧是 9，右侧是 15,20,7，分别递归构造左右子树。
示例 2
输入：inorder = [-1], postorder = [-1] 输出：[-1]
解释：只有一个节点。
数据范围
1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000- 两个数组中的值各不相同。
postorder中的每个值都能在inorder中找到。- 输入一定是同一棵树合法的中序和后序遍历。
解题思路：递归 + 哈希表
后序遍历的最后一个数一定是根。在中序里找到根的位置 mid，左边是左子树，右边是右子树。后序的顺序是“左、右、根”，从末尾往前读就是“根、右、左”，所以每次从 postorder 末尾弹出一个值作根，先递归建右子树，再建左子树。用哈希表记录每个值在中序中的下标，查找 O(1)。
为什么正确
调用 build(lo, hi) 时，postorder 末尾的值正好是中序区间 inorder[lo..hi] 这棵子树的根。
复杂度分析
时间 O(n)，空间 O(n)（哈希表与递归栈）。
易错点
从后序末尾弹出时必须先建右子树、再建左子树。顺序反了，弹出的值会对应到错误的子树。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
idx = {v: i for i, v in enumerate(inorder)}
def build(lo, hi):
if lo > hi:
return None
val = postorder.pop()
root = TreeNode(val)
mid = idx[val]
root.right = build(mid + 1, hi)
root.left = build(lo, mid - 1)
return root
return build(0, len(inorder) - 1)class Solution {
Map<Integer, Integer> idx = new HashMap<>();
int[] postorder;
int p;
public TreeNode buildTree(int[] inorder, int[] postorder) {
for (int i = 0; i < inorder.length; i++) idx.put(inorder[i], i);
this.postorder = postorder;
p = postorder.length - 1;
return build(0, inorder.length - 1);
}
TreeNode build(int lo, int hi) {
if (lo > hi) {
return null;
}
int val = postorder[p--];
TreeNode root = new TreeNode(val);
int mid = idx.get(val);
root.right = build(mid + 1, hi);
root.left = build(lo, mid - 1);
return root;
}
}class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
unordered_map<int, int> idx;
for (int i = 0; i < (int)inorder.size(); i++) idx[inorder[i]] = i;
function<TreeNode*(int, int)> build = [&](int lo, int hi) -> TreeNode* {
if (lo > hi) {
return nullptr;
}
int val = postorder.back();
postorder.pop_back();
TreeNode* root = new TreeNode(val);
int mid = idx[val];
root->right = build(mid + 1, hi);
root->left = build(lo, mid - 1);
return root;
};
return build(0, (int)inorder.size() - 1);
}
};func buildTree(inorder []int, postorder []int) *TreeNode {
idx := map[int]int{}
for i, v := range inorder {
idx[v] = i
}
var build func(lo, hi int) *TreeNode
build = func(lo, hi int) *TreeNode {
if lo > hi {
return nil
}
val := postorder[len(postorder)-1]
postorder = postorder[:len(postorder)-1]
root := &TreeNode{Val: val}
mid := idx[val]
root.Right = build(mid+1, hi)
root.Left = build(lo, mid-1)
return root
}
return build(0, len(inorder)-1)
}var buildTree = function(inorder, postorder) {
const idx = new Map(inorder.map((v, i) => [v, i]));
const build = (lo, hi) => {
if (lo > hi) {
return null;
}
const val = postorder.pop();
const root = new TreeNode(val);
const mid = idx.get(val);
root.right = build(mid + 1, hi);
root.left = build(lo, mid - 1);
return root;
};
return build(0, inorder.length - 1);
};function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
const idx = new Map(inorder.map((v, i) => [v, i]));
const build = (lo: number, hi: number): TreeNode | null => {
if (lo > hi) {
return null;
}
const val = postorder.pop()!;
const root = new TreeNode(val);
const mid = idx.get(val)!;
root.right = build(mid + 1, hi);
root.left = build(lo, mid - 1);
return root;
};
return build(0, inorder.length - 1);
}其他解法
递归 + 哈希表按区间划分，最好理解；迭代法用栈模拟沿右链下行和回溯，省去哈希表和递归栈。
解法 2：迭代（栈） 时间 O(n)，空间 O(h)
从后往前读后序序列，它是“根、右、左”的顺序；中序指针 idx 也从末尾开始。栈顶值不等于 inorder[idx] 时，新节点是栈顶的右孩子。相等时不断出栈并左移 idx，新节点是最后一个出栈节点的左孩子。新节点总是入栈。
不需要哈希表，也没有递归，深链树不会栈溢出。它是第 105 题迭代法的镜像，左右和方向全部对调，要先理解那一版。
class Solution:
def buildTree(self, inorder, postorder):
if not postorder:
return None
root = TreeNode(postorder[-1])
stack = [root]
idx = len(inorder) - 1
for i in range(len(postorder) - 2, -1, -1):
node = stack[-1]
if node.val != inorder[idx]:
node.right = TreeNode(postorder[i])
stack.append(node.right)
else:
while stack and stack[-1].val == inorder[idx]:
node = stack.pop()
idx -= 1
node.left = TreeNode(postorder[i])
stack.append(node.left)
return rootclass Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (postorder.length == 0) return null;
int n = postorder.length;
TreeNode root = new TreeNode(postorder[n - 1]);
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
int idx = n - 1;
for (int i = n - 2; i >= 0; i--) {
TreeNode node = stack.peek();
if (node.val != inorder[idx]) {
node.right = new TreeNode(postorder[i]);
stack.push(node.right);
} else {
while (!stack.isEmpty() && stack.peek().val == inorder[idx]) {
node = stack.pop();
idx--;
}
node.left = new TreeNode(postorder[i]);
stack.push(node.left);
}
}
return root;
}
}class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (postorder.empty()) return nullptr;
int n = postorder.size();
TreeNode* root = new TreeNode(postorder[n - 1]);
vector<TreeNode*> stack{root};
int idx = n - 1;
for (int i = n - 2; i >= 0; i--) {
TreeNode* node = stack.back();
if (node->val != inorder[idx]) {
node->right = new TreeNode(postorder[i]);
stack.push_back(node->right);
} else {
while (!stack.empty() && stack.back()->val == inorder[idx]) {
node = stack.back();
stack.pop_back();
idx--;
}
node->left = new TreeNode(postorder[i]);
stack.push_back(node->left);
}
}
return root;
}
};func buildTree(inorder []int, postorder []int) *TreeNode {
n := len(postorder)
if n == 0 {
return nil
}
root := &TreeNode{Val: postorder[n-1]}
stack := []*TreeNode{root}
idx := n - 1
for i := n - 2; i >= 0; i-- {
node := stack[len(stack)-1]
if node.Val != inorder[idx] {
node.Right = &TreeNode{Val: postorder[i]}
stack = append(stack, node.Right)
} else {
for len(stack) > 0 && stack[len(stack)-1].Val == inorder[idx] {
node = stack[len(stack)-1]
stack = stack[:len(stack)-1]
idx--
}
node.Left = &TreeNode{Val: postorder[i]}
stack = append(stack, node.Left)
}
}
return root
}var buildTree = function(inorder, postorder) {
const n = postorder.length;
if (!n) return null;
const root = new TreeNode(postorder[n - 1]);
const stack = [root];
let idx = n - 1;
for (let i = n - 2; i >= 0; i--) {
let node = stack[stack.length - 1];
if (node.val !== inorder[idx]) {
node.right = new TreeNode(postorder[i]);
stack.push(node.right);
} else {
while (stack.length && stack[stack.length - 1].val === inorder[idx]) {
node = stack.pop();
idx--;
}
node.left = new TreeNode(postorder[i]);
stack.push(node.left);
}
}
return root;
};function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
const n = postorder.length;
if (!n) return null;
const root = new TreeNode(postorder[n - 1]);
const stack: TreeNode[] = [root];
let idx = n - 1;
for (let i = n - 2; i >= 0; i--) {
let node = stack[stack.length - 1];
if (node.val !== inorder[idx]) {
node.right = new TreeNode(postorder[i]);
stack.push(node.right);
} else {
while (stack.length && stack[stack.length - 1].val === inorder[idx]) {
node = stack.pop()!;
idx--;
}
node.left = new TreeNode(postorder[i]);
stack.push(node.left);
}
}
return root;
};