Data Struct coding List

数据结构题单

该博客基于本人在备考研究生时学习408数据结构过程中刷过的相关题目,感兴趣的同学也可以进行尝试。 ## 链表 #### 删除节点

设计链表

• 能否独立完成 自己写还是会出现各种各样的bug，有待提高

反转链表

• 头插法
• 递归做法

两数相加

• 暴力运算 + 尾插法 ps：其实和标准题解的时间复杂度基本一致都是O(m + n)但实际的执行时间只超过50

交换节点

• 正常解法

值得注意的地方是第一次交换的时候头节点会变成链表的第二个元素，倘若直接返回head会导致链表丢失首元素。

head
[0] -> [1] -> [...]

       head
[1] -> [0] -> [...]

删除节点

• 正常做法，这个遍历一遍求链表长度的操作是必不可少的，递归的开销一定比普通做法大。

链表相交

• 先求两链表长度，指向长链表的指针先向前移动两链表长度差单位，然后两指针同时向前，当两指针第一次相同时就找到了链表相交的点 ps:408统考2012年真题

环形链表

• 值判断有没有环，相较于II简单很多，图一乐

环形链表II

• 使用快慢指针判断链表中是否有环，有环的情况下从相遇的位置开始，再建立一个新的指针从链表头开始同慢指针一起以1的速度前进，两者第一次相遇的位置就是环的入口 ps:

1. 不需要建立统一头节点，快慢指针直接从链表的第一个元素开始
2. 先移动快慢指针，再判断快慢指针是否相等。

合并有序链表

• 比两数之和简单，可以不用做

旋转链表

• 先将链表闭合成环，要旋转的单位如果为链表长度的整数倍则什么都不做，否则将第(len - k)个元素作为新的尾巴；

回文链表

• 用栈辅助判断。
• [ ]

删除元素

• 双指针法，快指针往前走，如果快慢指针指向的元素值不一样slow->next 指向快指针，slow向前移动，直到fast->next为空。最后检测solw释放后等于fast，如果等于slow直接指向nullptr

删除元素II

• 没有必要使用两个指针，这样会使得逻辑判断更加混乱。

分隔链表

• 使用两个链表来操作。

反转链表

• 原地开转，有点理解难度

栈与队列

使用栈实现队列

• 理论基础还是很简单的，不过需要注意一个细节：

stack的pop()操作只删除，返回void，但队列的pop()要返回弹出的值，所以：

在进行pop操作的时候要先保存stack的栈顶元素，将stack的栈顶元素弹出后返回刚刚保存的值

int pop() {
    while(!f.empty()){
         b.push(f.top());
         f.pop();
    }
    if(!b.empty()) {
        int ans = b.top();
        b.pop();
        return ans;
    }
    return -1;
}

使用队列模拟栈

• 栈模拟队列并不直观，操作略显笨拙。

括号匹配

• 简单

删除字符串中的所有相邻重复项

• 简单

逆波兰表达式的计算

• 简单

滑动窗口最大值

• 单调队列详细笔记

二叉树

二叉树的前序遍历(迭代)

• 使用栈模拟前序遍历

二叉树的后序遍历(迭代)

• 使用栈模拟后序遍历

前序遍历的顺序是 中、左、右，而后序遍历的顺序是左，右、中。我们可以在先序遍历的时候调整顺序遍历中、右、左，然后将保存的result序列反向输出得到后序遍历的结果。

二叉树的中序遍历(迭代)

• 使用栈模拟中序遍历 中序遍历迭代详细笔记

二叉树的层序遍历

• 正常做法使用栈模拟即可，但这道题要求分层保存

使用两个二维vector第一个存放Treenode*记录前一层的节点，第二个用以存放结果。遍历这一层的所有节点，将他们的左右子节点放下一层的vector中，如果它们都没有子节点则结束循环。层序遍历迭代详细笔记

二叉树的层序遍历(II)

• 上一题的结果reverse(result.begin(),result.end())以下即可

二叉树的右视图

• 上一题的结果稍加改造即可

PS：虽然都大差不差，但是还是建议自己多敲几遍加深印象~，一味的复制粘贴并没有什么意义。

反转二叉树

• 在前序和后序的基础上都可以，但中序不可以，因为中序在反转完左子树后该节点反转，再去反转的右子树其实是之前反转过的左子树。

对称二叉树

• 有点钻牛角尖把简单问题复杂化了，建议重做

二叉树的最大深度

• 另开一个栈，用于记录当前节点的深度。

N叉树的最大深度

• 多叉树用层序遍历做很简单。

二叉树的最小深度

• 思路其实和最大深度差不多，把判定放在叶节点做就可以了。

2025-06-17

位运算结合折半查找计算完全二叉树的节点个数

• 折半查找 + 节点编号与节点位置的关系，值得细品。

判断AVL树

• 递归查找，求树的深度使用前序遍历，求树的高度使用后序遍历

二叉树的所有路径

• 递归、轮椅。

左叶子的和

本质还是遍历，途中顺带确认一下有没有符合条件的节点。 - [x] 递归、轮椅。 - [x] 迭代未必不会更简单。

找树左下角的值

• 层序遍历秒了。

路径总和

• 递归注意判断的是子节点而非等到访问空节点再判断

做不动了做不动了，歇逼了兄弟们。

2025-06-19

后序中序构造二叉树

• 根据后序中序序列特性来递归构造二叉树，详细题解见：后序中序构造二叉树详细笔记

前序中序构造二叉树

• 思路同上，没有什么区别。

最大二叉树

• 思路类比上边，甚至更简单。

2025-06-20

合并二叉树

• 同时遍历两棵树，实际上很简单。

二叉搜索树中的搜索

• 很简单，但请记得二叉搜索树的定义。

验证二叉搜索树

• 不能简单地左节点大于右节点。按照中序遍历保存序列，然后再判断是否满足二叉搜索树的要求。

二叉搜索树的最小绝对差

• 沿用了上一题的暴力思路。

2025-06-21

二叉搜索树中的众数

• 因为是二叉搜索树所以可以和上面的思路一样先将中序序列保存，第一遍遍历找到一个众数出现了几次。第二遍遍历数组找导出现次数为众数出现次数的数加入到结果中。
• 使用pre指针记录前一个遍历过的节点。使用全局变量记录状态，详细笔记见：查找二叉搜索树中的众数详细笔记

二叉树的最近公共祖先

• 后序遍历自下向上搜索，详细笔记见：查找二叉树中的最近公共父节点

二叉搜索树中的插入操作

2025-06-22

二叉搜索树的最近公共祖先

• 根据二叉搜索树的性质，同时往下搜索p和q，直到用于搜索的两个指针分开时，则分开前的节点就是两节点的最近公共祖先。

二叉树展开为链表

• 使用栈模拟

2025-06-25

修剪二叉树

• 修剪二叉树