深度优先遍历 DFS
解题思路
如果只知道 前序遍历 和 后序遍历 的二叉树，则不一定是唯一的，如下图：
- 这两棵二叉树，前序遍历都是 1,2,3,4
- 这两棵二叉树，后序遍历都是 3,4,2,1
先回顾一下二叉树的前序、后序遍历
- 前序遍历是：根、左、右
- 后序遍历是：左、右、根
题目说 如果存在多个答案，可以返回其中任何一个，那么可以规定在 前序遍历 中，preorder[1] 是 左子树的根节点 值；
- 如果根据规定，preorder[1] 是 左子树的根节点 值，那么根据 preorder[1] 在 postorder 中的位置，确定了 preorder 左子树的长度、右子树的长度；
- 再根据确定的 preorder 左右子树的长度切分 postorder 的左右子树；
根据以上步骤，得到了左右子树的前序遍历、后序遍历，这是一个子问题，可以递归解决；
复杂度
-
时间复杂度：
O(N^2)，其中 n 为 preorder 的长度，最坏情况下二叉树是一条链，需要递归O(N)次，每次都需要O(N)的时间查找 preorder[1] 和 复制数组； -
空间复杂度：
O(N^2)；
实现代码
var constructFromPrePost = function (preorder, postorder) {
const n = preorder.length;
if (n === 0) return null; // 空节点
if (n === 1) return new TreeNode(preorder[0]); // 叶子节点，否则堆栈溢出
// 1. 根据先序遍历中的第二个左数根节点，找到后序遍历中的左树根的位置（可以算出左子树的大小）
const leftSize = postorder.indexOf(preorder[1]) + 1; // 左子树的大小
// 2. 根据左子树根节点，切割 前序 的左右子树
const pre1 = preorder.slice(1, 1 + leftSize);
const pre2 = preorder.slice(1 + leftSize);
// 3. 根据左子树根节点，切割 后序 的左右子树
const post1 = postorder.slice(0, leftSize);
const post2 = postorder.slice(leftSize, n - 1);
// 4. 递归构建左右子树
const left = constructFromPrePost(pre1, post1);
const right = constructFromPrePost(pre2, post2);
return new TreeNode(preorder[0], left, right);
};
深度优先遍历 DFS（空间换时间）
解题思路
用一个 哈希表 记录 postorder 每个元素的下标，这样就可以
O(1)查到 preorder[1] 在 postorder 的位置，从而O(1)知道左子树的大小；把递归参数改成子数组下标区间（左闭右开区间）的左右端点，从而避免复制数组；
复杂度
-
时间复杂度：
O(N)，其中 N 为 preorder 的长度，递归O(N)次，每次只需要O(1)的时间； -
空间复杂度：
O(N)；
实现代码
var constructFromPrePost = function (preorder, postorder) {
const n = preorder.length;
const hash = new Map();
// 1. hash 表记录后序内个元素的下标
for (let i = 0; i < n; i++) {
hash.set(postorder[i], i);
}
var dfs = (preL, preR, postL, postR) => {
if (preL === preR) { // 空节点
return null;
}
if (preL + 1 === preR) { // 叶子节点
return new TreeNode(preorder[preL]);
}
const leftSize = hash.get(preorder[preL + 1]) - postL + 1; // 左子树的大小
const left = dfs(preL + 1, preL + 1 + leftSize, postL, postL + leftSize);
const right = dfs(preL + 1 + leftSize, preR, postL + leftSize, postR - 1);
return new TreeNode(postorder[postR - 1], left, right);
}
// 2. 递归遍历
return dfs(0, n, 0, n); // 左闭右开区间
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 106. 从中序与后序遍历序列构造二叉树
上一篇
评论
