重建二叉树
图解：
复杂度：
-
时间复杂度：O(N)；其中 N 为树的节点数量；递归共建立 N 个节点，每层递归中的节点建立、搜索操作占用 O(1)，因此使用 O(N) 时间；
-
空间复杂度：O(N)，最差情况下（输入二叉树为链表时），递归深度达到 N，占用 O(N) 的栈空间；
代码实现：
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
if (preorder.length === 0 || inorder.length === 0) return null;
// 前序遍历的第一个节点定然是当前树的根节点，构建树节点
const root = new TreeNode(preorder[0]);
// 拿 root 把中序遍历的数组劈开，左边为左子树，右边为右子树
let rootIndex = inorder.findIndex(item => item === preorder[0]);
if (rootIndex === -1) return null;
preorder.shift(); // 删除掉先序遍历的根节点
// 左边的数组定然全部都是当前根节点的左子树上的节点
root.left = buildTree(preorder, inorder.slice(0, rootIndex));
// 右边的数组定然全部都是当前根节点的右子树上的节点
root.right = buildTree(preorder, inorder.slice(rootIndex + 1));
return root;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
第 5️⃣ 座大山：防抖和节流
上一篇
评论
