心谭

题解

/ 注册

全部文章 / 题解（共22篇）

剑指offer - 二叉树中和为某一值的路径 - JavaScript

【二叉树中和为某一值的路径】【2种解法：递归 + 非递归】解法 1: 前序遍历（递归）算法实现思路是：每次来到新节点，将节点放入当前保存的路径检查节点是否是叶节点：是：将路径放入结果中不是：继续遍历左子树和右子树上面整个过程就是一个前序遍历，但在遍历的过程中，动态地维护了当前路...

剑指offer 算法二叉树

2020-02-08

0 927

剑指offer - 复杂链表的复制 - JavaScript

【复杂链表的复制】【JavaScript解法】思路用一个哈希表表示映射关系：键是原节点，值是复制的节点。整体算法流程是：第一次遍历，复制每个节点和 next 指针，并且保存“原节点-复制节点”的映射关系第二次遍历，通过哈希表获得节点对应的复制节点，更新 random 指针代码实现使...

剑指offer 算法哈希表

2020-02-08

4 1385

剑指offer - 二叉搜索树与双向链表

【二叉搜索树与双向链表】【2种解法（一次递归或递归+遍历）】题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。解法 1: 一次递归（推荐）二叉搜索树的性质是：左节点 < 当前节点 < 右节点。转换后的双向...

算法递归二叉树二叉搜索树

2020-02-08

8 1439

剑指offer - 数组中出现次数超过一半的数字（2种解法）

【数组中出现次数超过一半的数字】【剑指offer】【2种解法】题目描述数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为 9 的数组{1,2,3,2,2,2,5,4,2}。由于数字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 2。如果不存在则输出 0。...

剑指offer 算法数组哈希表

2020-02-08

1 1073

剑指offer - 二叉搜索树的后续遍历序列

【二叉搜索树的后续遍历序列】【剑指offer】【JavaScript版】思路这题主要考察的是后序遍历的特点和二叉搜索树的特点。根据定义，后序遍历结果的最后一个元素就是当前二叉树的根元素。结合二叉搜索树左子节点 > 根节点 > 右子节点的特点，我们可以找到左右子树的元素。例如下面...

剑指offer 算法二叉树二叉搜索树 javascript 数据结构

2020-02-03

4 1189

剑指offer - 栈的压入弹出序列

需要一个辅助栈，来模拟出入栈的过程。算法流程如下：取压入队列的首元素，将其压入辅助栈检查辅助栈顶元素是否和弹出队列的首元素相等：若相等，则辅助栈弹出栈顶元素，弹出队列取出队首元素，重复检查若不相等，回到第一步最后，检查辅助栈和弹出队列是否均为空。时间复杂度是 O(N^2)，空间复...

剑指offer 算法栈

2020-02-02

1 840

剑指offer - 顺时针打印矩阵（2种解法）

【顺时针打印矩阵】【2种解法】【剑指offer】这一题和Leetcode 54.螺旋矩阵一模一样。解法 1: 模拟路径根据直觉，当遍历的过程中，遇到超出边界 / 元素已经被访问过的情况时，应该按照顺时针转变方向。假设给定的矩阵的形状是 m*n，那么一共要遍历 m*n 次。要准备一个长度为 m*...

剑指offer 算法数组

2020-02-02

1 992

剑指offer - 包含min函数的栈（2种解法）

【包含min函数的栈】【2种解法】【剑指offer】解法 1: 暴力法直接遍历栈得到最小的元素，但理论上 min 函数的时间复杂度是 O(N)，显然不符合题目要求。注意：可能由于 js 本身的原因，在牛客网的平台上 ac，这种方法的耗时最少。解法 2: 辅助栈正确的做法是借助一个辅助栈。他...

剑指offer 算法栈数组队列

2020-02-02

3 977

剑指offer - 合并两个排序的链表

设置一个“哨兵节点”叫 preHead，这会让代码写起来非常“清爽”。整体流程如下：如果 pHead1 和 pHead2，均没遍历完：如果 pHead1.val <= pHead2.val，那么当前 node 的 next 指向 pHead1。并且移动 pHead1 指针。否则，当前 ...

剑指offer 算法前端链表 javascript

2020-01-18

9 1375

剑指offer - 树的子结构

为了方便说明，先看两个例子。例子 1 下图是第一个例子，可以看到 B 是 A 的子结构。第一个例子的判断逻辑是：比较当前节点值递归比较左右节点的值直到遍历完 B 树例子 2 下图是第二个例子，可以看到 B 也是 A 的子结构。但是 A 的根节点和 B 的根节点并不相同。因此对于...

剑指offer 算法二叉树 javascript

2020-01-18

23 1311