asp网站开发视频,嵌入式软件开发文档,家政服务app软件开发,网络公司代理文章目录题目递归思路细节易错代码复杂度分析迭代思路细节易错代码复杂度分析题目
输入某二叉树的前序遍历和中序遍历的结果#xff0c;请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如#xff0c;给出 前序遍历 preorder [3,9,20,15,7] 中…
文章目录题目递归思路细节易错代码复杂度分析迭代思路细节易错代码复杂度分析题目
输入某二叉树的前序遍历和中序遍历的结果请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如给出 前序遍历 preorder [3,9,20,15,7] 中序遍历 inorder [9,3,15,20,7] 返回如下的二叉树 限制 0 节点个数 5000 递归
思路
首先要明确最重要的一个知识
对于任意一颗树而言前序遍历的形式总是 [ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ] 即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是 [ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ] 显然
对前序遍历来讲找到左右子树的遍历结果分界线是困难的找到根节点是简单的对中序遍历来讲找到根节点是困难的但找到根节点之后左右两侧自然分成左右两棵子树
根据上面的特性我们可以做出互补
通过前序遍历的结果数组的首元素确定根节点根据找到的根节点结合中序遍历数组确定左右子树的节点数目
重复上述过程我们也就可以通过将每个节点视作根节点不断递归生成左右子树无法再生成左右子树。很显然生成左右子树的过程可以用递归思想来实现。 细节
思路有了仍需解决几个问题
即使通过前序遍历找到根节点怎样确定根节点在中序遍历中的位置递归生成左右子树的细节操作是什么
先解决第一个问题
普通的方法当然是拿着根节点的值从中序遍历结果数组inorder [0]开始遍历但是每次在生成根节点时都进行遍历的话时间复杂度较高O(N)。因此可以使用哈希表来建设中序遍历数组值到下标的键值对映射。
在构造二叉树的过程之前我们可以对中序遍历的列表进行一遍扫描O(N)就可以构造出这个哈希映射。
在此后构造二叉树的过程中我们就只需要 O(1)的时间对根节点进行定位了。一次O(N)N次O(1)否则我们必须每次都遍历一遍中序遍历结果数组定位根节点N次O(N)。
再来说第二个问题
递归生成左右子树这种说法听起来还是太“模糊”了其实我们实际做的操作是不停的生成根节点再进入这个根节点的左右子树在每个子树中生成当前子树的根节点直到这个”根节点“没有子树为止。
易错
写代码的时候没有子树应该返回空指针——return nullptr;粗心大意写成了return nullnull和nullptr是有区别的。
代码
class Solution {
private:mapint, int index; // 映射值给定值对应的下标
public:TreeNode* buildTree(vectorint preorder, vectorint inorder) {int num inorder.size();for (int i 0; i num; i){index[inorder[i]] i; // 建立中序遍历数组 值到下标 的键值对映射快速定位根节点}return buildRoot(preorder, inorder, 0, num - 1, 0, num - 1);}// 把每个节点都当作它自身的“根节点”进入到每个节点遍历生成它的左右子树、及根节点本身 TreeNode* buildRoot(vectorint pre, vectorint in, int pre_left, int pre_right, int in_left, int in_right) {if (pre_left pre_right) { // 没有子树return nullptr;}int pre_root pre_left; // 前序遍历的根节点就是左边界int in_root index[pre[pre_left]]; // 根据映射关系确定中序遍历中的根节点TreeNode* root new TreeNode(in[in_root]); // 建立根节点// 等价于TreeNode root TreeNode(in[in_root]);// TreeNode *proot root;// 但没必要这样写可能便于理解但是过于繁琐int lefttree_num in_root - in_left; // 确定左子树中节点数目// 前序遍历 根节点左边界1 到 根节点左子树数量 的范围为左子树// 中序遍历根节点左侧为左子树root-left buildRoot(pre, in, pre_left 1, pre_left lefttree_num, in_left, in_root - 1); // 前序遍历 根节点左子树数量1 到 右边界 的范围为右子树// 中序遍历根节点右侧为右子树root-right buildRoot(pre, in, pre_left 1 lefttree_num, pre_right, in_root 1, in_right);return root;}
};复杂度分析
时间复杂度O(n)其中 n 是树中的节点个数。
空间复杂度O(n)除去返回的答案需要的 O(n)空间之外我们还需要使用 O(n) 的空间存储哈希映射以及 O(h)其中 h 是树的高度的空间表示递归时栈空间。这里 h n所以总空间复杂度为 O(n)。 迭代
思路
前序遍历的相邻节点 u 和 v 有如下关系
v 是 u 的左儿子u 没有左儿子。则 v 是 u 或者 u 祖先节点的右儿子。
以此树为例 它的前序遍历和中序遍历分别为 preorder [3, 9, 8, 5, 4, 10, 20, 15, 7] inorder [4, 5, 8, 10, 9, 3, 15, 20, 7] 可以看到对于39854它们之间满足第一种关系例如8是9的左儿子对于410它们满足第二种关系10是4祖父节点的右儿子。
也就是前序遍历会
从根节点开始一直遍历左子树直到左子树遍历完了开始遍历右子树如果当前的节点没有右子树则会回溯遍历祖先节点的右子树。
那么我们可以根据这一特性我们可以用一个栈来存储祖先节点和左子树直到左子树被遍历完本例中将39854依次入栈直到遇到10此时开始寻找当前节点10是谁的右儿子。
细节
思路有了仍需解决几个问题
当开始遍历右子树怎么确定当前节点是谁的右儿子呢
这时来看中序遍历我们可以发现中序遍历结果数组的首元素是——根节点不断往左走达到的最终节点。 根据这一特性我们可以创建一个指针 index 指向当前的最左子树。
首先我们将根节点 3 入栈再初始化 index 指向的节点为 4随后对于前序遍历中的每个节点我们依次判断它是栈顶节点的左儿子还是栈中某个节点的右儿子。
我们遍历 9。9 一定是栈顶节点 3 的左儿子。我们使用反证法假设 9 是 3 的右儿子那么 3 没有左儿子index 应该恰好指向 3但实际上为 4因此产生了矛盾。所以我们将 9 作为 3 的左儿子并将 9 入栈。 stack [3, 9] index - inorder[0] 4 我们遍历 85 和 4。同理可得它们都是上一个节点栈顶节点的左儿子所以它们会依次入栈。 stack [3, 9, 8, 5, 4] index - inorder[0] 4 当我们遍历到 10这时情况就不一样了。我们发现此时 index 指向的节点和当前的栈顶节点一样都为 4也就是说 4 没有左儿子那么 10 必须为栈中某个节点的右儿子。 那么如何找到这个节点呢栈中的节点的顺序和它们在前序遍历中出现的顺序是一致的而且每一个节点的右儿子都还没有被遍历过 那么这些节点的顺序和它们在中序遍历中出现的顺序一定是相反的原因如下。 这是因为栈中的任意两个相邻的节点前者都是后者的某个祖先。并且我们知道栈中的任意一个节点的右儿子还没有被遍历过前序遍历顺序——中左右说明后者一定是前者左儿子那么后者就先于前者出现在中序遍历中中序遍历顺序——左中右。 因此我们可以先把此时的栈顶元素保存并弹出 然后把 index 不断向右移动并与栈顶节点进行比较。如果 index 对应的元素恰好等于栈顶节点那么说明上一个被弹出的节点没有右子树且其本身是当前节点的左子树 所以重复将栈顶节点保存并弹出然后将 index 增加 1 的过程直到 index 对应的元素不等于栈顶节点此时 index 对应的元素就是上一个被保存且弹出的栈顶节点的右子树。按照这样的过程我们弹出的最后一个节点 x 就是 10 的父节点这是因为 10 出现在了 x 与 x在栈中的下一个节点的中序遍历之间因此 10 就是 x 的右儿子根据中序遍历顺序——左中右x是中10是右x在栈中的下一个节点是x的父节点。 回到我们的例子我们会依次从栈顶弹出 45 和 8并且将 index 向右移动了三次。我们将 10 作为最后弹出的节点 8 的右儿子并将 10 入栈。 stack [3, 9, 10] index - inorder[3] 10 我们遍历 20时。index 恰好指向当前栈顶节点 10那么我们会依次从栈顶弹出 109 和 3并且将 index 向右移动了三次。我们将 20 作为最后弹出的节点 3 的右儿子并将 20 入栈。 stack [20] index - inorder[6] 15 我们遍历 15将 15 作为栈顶节点 20 的左儿子并将 15 入栈。 stack [20, 15] index - inorder[6] 15 我们遍历 7。index 恰好指向当前栈顶节点 15那么我们会依次从栈顶弹出 15 和 20并且将 index 向右移动了两次。我们将 7 作为最后弹出的节点 20 的右儿子并将 7 入栈。 stack [7] index - inorder[8] 7 此时遍历结束我们构造出了正确的二叉树。
总结来讲就是遍历前序遍历结果数组并将其压到栈中
当栈顶元素不等于index指向的元素时将当前元素作为栈顶元素的左儿子然后当前元素入栈成为新栈顶。当栈顶元素等于index指向的元素时弹出并保存栈顶元素同时将index递增1再判断栈顶元素和index指向的元素之间的关系相等则重复上述操作不相等则将当前元素作为最后一个被弹出的栈顶元素的右儿子然后将当前元素入栈成为新栈顶。
易错
通过判断前序遍历或中序遍历的结果数组是否为空来确定二叉树是否为空。二叉树不为空时在建立左右子树的循环操作之前先将根节点入栈。因为根节点的建立操作与其他左右子树不同放到循环里面要单独处理反而繁琐。注意保存弹出的栈顶元素。在生成右子树的时候栈不为空也应该是重要的循环判定条件之一。
代码
class Solution2 { // 迭代
public:TreeNode* buildTree(vectorint preorder, vectorint inorder) {if (!preorder.size()) {return nullptr;}stackTreeNode* st;TreeNode* root new TreeNode(preorder[0]); // 建立根节点st.push(root); // 根节点入栈// 否则无法进行将节点归为左儿子或者右儿子的操作// 因为进行上面的操作需要访问栈顶元素的left或者rightint index 0;for (size_t i 1; i preorder.size(); i) {int pre preorder[i];int in inorder[index];auto node st.top();if (node-val ! in) { // 如果前序遍历i位置的数和中序遍历index位置的数不相等// 说明i位置的数是二叉树的左子树node-left new TreeNode(pre);st.push(node-left);}else {while (!st.empty() in st.top()-val) {in inorder[index];node st.top(); // 保存弹出的节点// 当跳出while时pre的值即为该节点右子树st.pop();}node-right new TreeNode(pre);st.push(node-right);}}return root;}
};复杂度分析
时间复杂度O(n)其中 n 是树中的节点个数。
空间复杂度O(n)除去返回的答案需要的 O(n) 空间之外我们还需要使用 O(h)其中 h 是树的高度的空间存储栈。这里 h n所以在最坏情况下总空间复杂度为 O(n)。
