深度优先遍历 DFS
解题思路
给定了 中序遍历 inorder = [9, 3, 15, 20, 7] 和 后序遍历 postorder = [9, 15, 7, 20, 3] 序列，中序遍历的顺序是 左、根、右，后序遍历的顺序是 左、右、根；
- 根据后序遍历的第最后个元素，可得知
3是根节点，其他节点确定不下来；- 对 中序遍历 进一步来判断， 可得知 [(9 左), (3 根), (15, 20, 7 右)] 中的左子树 和 右子树；
- 根据 中序遍历 则可知 preorder 的 [9 左), (15, 7, 20 右), (3 根)] 中的左子树 和 右子树；
根据以上步骤，得到了左右子树的中序遍历、后序遍历，这是一个子问题，可以递归解决；
复杂度
-
时间复杂度：
O(N^2)，其中 n 为 postorder 的长度，最坏情况下二叉树是一条链，需要递归O(N)次，每次都需要O(N)的时间查找 postorder[N - 1] 和 复制数组； -
空间复杂度：
O(N^2)；
代码实现
var buildTree = function (inorder, postorder) {
const n = postorder.length;
if (n === 0) return null; // 空节点
// 1. 根据后序遍历中的最后一个节点（根节点），找到中序遍历中的根的位置（可以算出左子树的大小）
const leftSize = inorder.indexOf(postorder[n - 1]);
// 2. 根据根节点，切割 后序 的左右子树
const pos1 = postorder.slice(0, leftSize);
const pos2 = postorder.slice(leftSize, n - 1);
// 3. 根据根节点，切割 中序 的左右子树
const in1 = inorder.slice(0, leftSize);
const in2 = inorder.slice(1 + leftSize, n);
// 4. 递归构建左右子树
const left = buildTree(in1, pos1);
const right = buildTree(in2, pos2);
return new TreeNode(postorder[n - 1], left, right);
};
深度优先遍历 DFS（空间换时间）
解题思路
用一个 哈希表 记录 inorder 每个元素的下标，这样就可以
O(1)查到 postorder[N - 1] 在 inorder 的位置，从而O(1)知道左子树的大小；把递归参数改成子数组下标区间（左闭右开区间）的左右端点，从而避免复制数组；
复杂度
-
时间复杂度：
O(N)，其中 N 为 postorder 的长度，递归O(N)次，每次只需要O(1)的时间； -
空间复杂度：
O(N)；
代码实现
var buildTree = function (inorder, postorder) {
const n = inorder.length;
const hash = new Map();
// 1. hash 表记录中序内个元素的下标
for (let i = 0; i < n; i++) {
hash.set(inorder[i], i);
}
var dfs = (inL, inR, postL, postR) => {
if (postL === postR) return null; // 空节点
const leftSize = hash.get(postorder[postR - 1]) - inL; // 左子树的大小
const left = dfs(inL, inL + leftSize, postL, postL + leftSize);
const right = dfs(inL + 1 + leftSize, inR, postL + leftSize, postR - 1);
return new TreeNode(postorder[postR - 1], left, right);
}
// 2. 递归遍历
return dfs(0, n, 0, n); // 左闭右开区间
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 105. 从前序与中序遍历序列构造二叉树
上一篇
评论
