TypechoJoeTheme

Toasobi的博客

Toasobi

网站页面
类目归类
搜索到 28 篇与 的结果 ———
2023-03-22

二叉搜索树与双向链表（中等）
二叉搜索树与双向链表（中等）
这道题当时没做出来，其实是已经想到了使用中序遍历（中序遍历得到的结果就是链表的顺序）。但是不知道如何进行链表节点之间的连接。后面也思考到了每个子树的最右节点下一个连接的是根节点，这个其实就是中序遍历的思维后面看了题解知道了，可以设置两个全局变量，一个head，一个pre。head用于记录最后返回的结果（头节点），pre用于记录每次递归遍历到的节点的前一个节点，用于两点间连接。最后还要将首位相连（head.left = pre; pre.right = head;）此题得解代码如下：<div>class Solution { Node head, pre; public Node treeToDoublyList(Node root) { if(root==null) return null; dfs(root); head.left = pre; pre.right = head; return head; } public void dfs(Node ro...
2023-03-22

剑指offer（第二版）

0 阅读
0 评论
2023年03月22日
0 阅读
0 评论
2023-03-20

复杂链表的复制（中等）
复杂链表的复制（中等）
这道题使用哈希表！感觉思路非常清奇！我们不同于以前复制简单链表那样使用双指针边动边复制，因为这个node除了存储next之外还有一个random。因为random可以指向随便一个node，所以这道题我们需要一个快速映射所有节点的方法，那就是哈希！我们将复制出来的节点每一个与旧节点进行映射，一一对应，那在构造新链表的next和random的时候，我们只需要使用旧链表的next和random的新链表的映射即可。代码如下：<div>class Solution { class Solution { public Node copyRandomList(Node head) { if(head == null) return null; Node cur = head; Map<Node, Node> map = new HashMap<>(); // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射 while(cur != nu...
2023-03-20

剑指offer（第二版）

0 阅读
0 评论
2023年03月20日
0 阅读
0 评论
2023-03-20

二叉树中和为某个值的路径（中等）
二叉树中和为某个值的路径（中等）
这道题的主要思路也是dfs，每次往下搜一次，目标数字要减去当前节点的val值。我们使用了一个list叫path来存储每一次搜索下去时经过的节点的val值。如果左右边都走过了还是不满足条件，则会将path中的值移除一个（回溯）注意res.add(new LinkedList(path)),这个比较关键，不能res.add(path),因为这样后面的path改变后list中的path也会更改。下面来看看代码：<div>class Solution { LinkedList<List<Integer>> res = new LinkedList<>(); LinkedList<Integer> path = new LinkedList<>(); public List<List<Integer>> pathSum(TreeNode root, int sum) { recur(root, sum); return res; ...
2023-03-20

剑指offer（第二版）

0 阅读
0 评论
2023年03月20日
0 阅读
0 评论
2023-03-20

二叉搜索树的后序遍历序列（中等）
二叉搜索树的后序遍历序列（中等）
这道题和根据前后遍历序列构造二叉树很相似，就是找到左右子树的范围，递归到只剩一个节点。结束的判断条件是：左子树的val全部小于根，右子树的val全部大于根，在此基础上指针偏移（看代码），最后一定得落在根节点上，否则不是该树的后序遍历。代码如下：<div>class Solution { public boolean verifyPostorder(int[] postorder) { return recur(postorder, 0, postorder.length - 1); } boolean recur(int[] postorder, int i, int j) { if(i >= j) return true; int p = i; while(postorder[p] < postorder[j]) p++; int m = p; //找左子树范围递归 while(postorder[p] > postorder[j...
2023-03-20

剑指offer（第二版）

0 阅读
0 评论
2023年03月20日
0 阅读
0 评论
2023-03-16

从上打印二叉树2（中等）
从上打印二叉树2（中等）
- 这题上一题是从上至下打印二叉树，其实就是层序遍历，**这题多了一个偶数高度的数组要逆转。** 上面是上一题的图。虽然是层序遍历，但是要求是每一层的数据都要一个list存储。所以这两道题的难点之一就是如何知道哪些数据是在同一个高度的，并将这些数据放入各个list中。而第二个难点就是逆转数组了对于如何知道数据是否在一个高度，我一开始的想法是用hashmap，key值存储高度，value存储数据。但是由于hashmap的key值不能重复只能就此作罢。我甚至想到了使用2的指数表示每一层的元素个数，同时使用一个int记录该层缺失多少元素。但是由于该层缺失多少元素非常难求，这个方法在只有一条线的二叉树面前直接寄掉了；；最后是题解给我的启发，在每次对队列添加完一层的元素后使用队列的长度作为for循环的临界值，每次for循环完成后表示一层的数据都遍历完成，在for循环中每遍历一个添加至一个list中，最后放入大list中，并重新new list（）将list全部重置。代码如下：<div>/** * Definition for a binary tree node. * pu...
2023-03-16

剑指offer（第二版）

0 阅读
0 评论
2023年03月16日
0 阅读
0 评论
Toasobi博主
暂无访问
125 文章数
1 评论量

互动读者

热门文章

2019 - 2020 © Reach - laolion

站点已稳定运行：

RSS MAP
当前在线1人博主 2023年10月12日 在线
繁