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