2024.06.22 刷题日记
199. 二叉树的右视图
这道题目的思路就是层次遍历,然后每次处理每一层所有的元素,如果是第一个就收集到答案中:
1 |
|
114. 二叉树展开为链表
思路是每次将找到当前节点的左子树的最右,然后当前节点的右子树挂在左子树的最右节点的右子树。接着遍历所有节点:
1 |
|
105. 从前序与中序遍历序列构造二叉树
这道题的思路是,使用递归,将先序序列的起始和结尾,以及中序序列的起始和结尾传入。接着preorder[preStart]
就是 root
节点,然后在中序中查找这个结点 p
(事实上,这里用 map 更快些),这个结点到中序的起始结点这一段就是 root
的左子树,另一半就是右子树,分别赋值给 root->left
、root->right
:
1 |
|
由于没用 map,所以时间复杂度高:
总结
199. 二叉树的右视图
算法思路:
- 使用层次遍历(广度优先搜索),从右向左处理每一层节点。
- 每层处理时,收集第一个节点的值作为该层的右视图节点。
核心点:
- 层次遍历。
- 每层第一个节点的值。
114. 二叉树展开为链表
算法思路:
- 遍历每个节点,将当前节点的左子树的最右节点找到,并将当前节点的右子树挂在这个最右节点的右子树上。
- 将左子树置为右子树,左子树置为空,然后继续处理下一个节点。
核心点:
- 找到左子树的最右节点。
- 调整节点链接,将树展开为链表。
105. 从前序与中序遍历序列构造二叉树
算法思路:
- 使用递归,根据前序遍历确定根节点,然后在中序遍历中找到根节点的位置,划分左右子树。
- 递归构造左子树和右子树,分别赋值给根节点的左右子节点。
核心点:
- 前序遍历的第一个节点是根节点。
- 在中序遍历中找到根节点位置以划分左右子树。
- 递归构造二叉树。
2024.06.22 刷题日记
http://blog.luliang.online/2024/06/23/2024.06.22 刷题日记/