2021.4.13-2021.4.18
涉及题目为 二叉树基础部分
第一周刷题结束后 进行一个简单总结
其中代码详细注释见每一天的刷题笔记 本总结部分只简单复现一遍代码！
题目参考开课吧某算法课程胡船长给出的内容~
| 题号 | 题名 |
|---|---|
| LC144 | 二叉树的前序遍历 |
| LC589 | N叉树的前序遍历 |
| LC226 | 翻转二叉树 |
| 剑指offer32 I | 从上到下打印二叉树 I |
| 剑指offer32 II == LC102 | 从上到下打印二叉树 II == 二叉树的层序遍历I |
| LC107 | 二叉树的层序遍历II |
| LC103 | 二叉树的锯齿形层序遍历 |
文章目录
LC144 二叉树的前序遍历
1.题目概述
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
2.代码逻辑
【1】定义preorder函数 用于进行递归 接下来进行preorder函数的完成
【2】设置退出条件
【3】将“当前”节点插入结果数组的结尾
【4】遍历当前节点的左子树 右子树
【5】主函数中先初始化数组 然后调用preorder函数 最后返回结果
3.C++代码
class Solution {
public:
void preorder(TreeNode *root,vector<int> &res) {
if (root == NULL) return;
res.emplace_back(root->val);
preorder(root->left, res);
preorder(root->right, res);
}
vector<int>preorderTraversal(TreeNode *root){
vector<int> res;
preorder(root, res);
return res;
}
};
4.python代码
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
def preorder(root: TreeNode):
if not root:
return
res.append(root.val)
preorder(root.left)
preorder(root.right)
res = list()
preorder(root)
return res
LC589 N叉树的前序遍历
1.题目概述
2.代码逻辑
整体跟二叉树的前序遍历差不多 区别在于 不能递归左子树+右子树 而是迭代容器中所有子节点
容器就是介个~
1.Npreorder函数
【1】退出条件
【2】插入尾部
【3】迭代所有元素并对每个元素进行递归遍历
2.调用
3.C++代码
class Solution {
public:
void Npreorder(Node *root, vector<int> &res){
if(root == NULL) return;
res.push_back(root->val);
for(auto x: root->children){
//迭代容器中所有的元素 每个元素的临时名字为x
//一直迭代到root没有子节点为止
Npreorder(x,res);//递归遍历
}
}
vector<int> preorder(Node* root) {
vector<int> res;
Npreorder(root, res);
return res;
}
};
4.python代码
class Solution:
def preorder(self, root: 'Node') -> List[int]:
res = []
def Npreorder(root):
if root:
res.append(root.val)
for node in root.children:
Npreorder(node)
Npreorder(root)
return res
LC226 翻转二叉树
1.题目概述
2.代码逻辑
【1】设置退出条件
【2】翻转每个节点的左子树和右子树
3.C++代码
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == nullptr) return root;
swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
};
4.python代码
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if not root:
return root
left = self.invertTree(root.left)
right = self.invertTree(root.right)
root.left, root.right = right, left
return root
剑指offer32 I 从上到下打印二叉树 I
1.题目概述
2.代码逻辑
【1】设置退出条件
如果根节点上来就是空的 直接返回结果——[]
【2】初始化结果数组 ans
【3】这里与前面不同了开始！
用到了队列来暂时存储树的节点（因为需要判断什么时候结束遍历~）
所以要初始化包含根节点的队列queue = [root]
二叉树的层序遍历用队列好想一些hhh
就是这个逻辑嘛~
【3】进行BFS循环（队列queue为空时跳出循环）
- 1.出队：队首元素出队
TreeNode* node = q.front() - 2.打印：将这个出队的元素放到结果数值末尾
- 3.添加子节点：
node的左（右）子节点如果不为空 则将左（右）子节点加入队列queue
【4】接下来来继续进行循环直到队列为空就行辽~
【5】返回打印结果数组ans
3.C++代码
class Solution {
public:
vector<int> levelOrder(TreeNode* root) {
vector<int> ans;
if (root == NULL) return ans;
queue<TreeNode*> q; //初始化队列
q.push(root);//根入队列
while(q.size()){
//BFS循环
TreeNode* node = q.front();
q.pop();
ans.push_back(node->val);
if(node->left)
q.push(node->left);
if(node->right)
q.push(node->right);
}
return ans;
}
};
4.python代码
class Solution:
def levelOrder(self, root: TreeNode) -> List[int]:
if not root:return []
res,queue = [],collections.deque()
#初始化 创建空结果列表 队列
queue.append(root) #节点入队
while queue:
node = queue.popleft()
#python可以不必把 “获取队首元素”&“队列首元素出队” 写成两句 一句解决~
res.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
return res
剑指offer32 II 从上到下打印二叉树II == LC102 二叉树的层序遍历
我的解题笔记
LC剑指offer32 从上到下打印二叉树II
1.题目概述
2.代码逻辑
C++
【1】深度优先函数的特例处理
【2】不断地往动态数组中创建新的行
【3】在每行中 不断地加入每层的节点
【4】逐个节点进行递归 每一个节点都进行【2】【3】操作
【5】调用时 从第0层开始就ok~
python
3.C++代码
class Solution {
public:
void getResult(TreeNode *root, int depth, vector<vector<int>> &ans){
//深度优先搜索
//这个是用于每一层打印结果的函数
if (root == NULL) return;//特例处理
if (depth == ans.size()) {
//在当前层数与最终结果（二维动态）数组的长度相同时
ans.push_back(vector<int>());//新建一行~
//在二维数组没有对应”行“的时候 新建这一“行”————就这作用~
}
ans[depth].push_back(root->val);//向结果数组的尾部中加入根节点
getResult(root->left, depth+1, ans);//逐层进行递归
getResult(root->right,depth+1, ans);
return;
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
getResult(root, 0, ans);//从第零层开始遍历
return ans;
}
};
4.python代码
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return [] #特例处理
res, queue = [], collections.deque() #初始化队列
queue.append(root) #把根压入队列
while queue: #队列只要不为空 就一直循环
tmp = [] #初始化临时列表
for _ in range(len(queue)): #当前层打印循环
node = queue.popleft() #队首元素出队 记为node 因为是双向队列 所以从左边出！
tmp.append(node.val) #将node加到结果列表中
if node.left: queue.append(node.left) #左子节点如果非空 加入队列末尾
if node.right: queue.append(node.right) #右子节点如果非空 加入队列末尾
res.append(tmp) #将这一层的结果打印出来 加到最后的二维结果数组中~
return res
LC107 二叉树的层序遍历II
1.题目概述
2.代码逻辑
不用说了
跟LC102几乎一样诶~
C++做个翻转
python做个翻转。。。
3.C++代码
class Solution {
public:
void getResult(TreeNode *root, int depth, vector<vector<int>> &ans){
if (root == NULL){
return;
}
if(depth == ans.size()){
ans.push_back(vector<int>());
}
ans[depth].push_back(root->val);
getResult(root->left, depth+1, ans);
getResult(root->right, depth+1, ans);
return;
}
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> ans;
getResult(root, 0, ans);//先常规从上到下打印出来二维数组
reverse(ans.begin(),ans.end());
return ans;
}
};
4.python代码
这…跟LC102有啥差别
就结尾返回ans[::-1]）（翻转结果数组）就行了
这就便捷得一批~
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if not root: return [];
ans,queue=[],collections.deque()
queue.append(root)
while queue:
tmp = []
for _ in range(len(queue)):
node = queue.popleft()#队首元素出队 因为是双向队列 所以从左边出！
tmp.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
ans.append(tmp)
return ans[::-1]
LC103 二叉树的锯齿形层序遍历
超级nice的一道题！
这题的刷题笔记记录了好多东西！
感觉前面刷了这么多二叉树相关的基础题
在这道题上都汇总起来了~
我的刷题笔记
LC103 二叉树的锯齿形层序遍历
1.题目概述
2.代码逻辑
依旧是熟悉的层序遍历
只不过变了下方向
C++
【1】定义总队列 装全部节点
【2】定义变量isOrderLeft 记录是否从左到右插入
【3】进入循环 循环终止条件为 总队列为空
【4】循环中 定义一个双端队列 levelList来存储当前层的值
【5】遍历当前层的值 并将所有值出队 之后将这些出队的值存入双端队列（如果isOrderLeft 为True就从左向右插入 为False就从右向左插入）
【6】将【4】【5】两步得到的当前层的结果添加到结果数组中
【7】（还在循环中嗷）做isOrderLeft = !isOrderLeft 操作 达到“偶数层反向遍历”的效果
【8】跳出循环 输出结果
python
取巧了23333 直接层序遍历加上指定层数翻转
【1】层序遍历
【2】指定层数（偶数层）翻转遍历结果数组（就是那个每层的一维结果数组啦）
3.C++代码
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
if(!root) return ans;
//利用队列实现 BFS按层遍历
queue<TreeNode*> nodeQueue;//定义一个TreeNode*类的队列 nodeQueue（这个解释不太清楚准不准确 是暂时的一个认知）
nodeQueue.push(root);
bool isOrderLeft = true;//记录是否是从左到右插入(true)
while (!nodeQueue.empty()){
//如果队列不为空 就一直循环下去
deque<int> levelList;//定义一个双端队列levelList来存储当层的值
int size = nodeQueue.size();//size存储了当前层的长度 方便下面对队列进行遍历
for (int i=0; i < size; i++){
//遍历总队列中该层的值并将所有值出队 按标志位存入双端队列 再按固定顺序读取下一层节点值进队列
auto node = nodeQueue.front();//取出队列第一个值 存储到node中
nodeQueue.pop();
if(isOrderLeft) {
//奇数层 从左到右插入双端队列
levelList.emplace_back(node->val);
}
else{
levelList.push_front(node->val);//从容器开头开始插入元素 实现从左往右插入双端队列
}
//接下来读取下一层节点值进入双端队列
if(node->left){
nodeQueue.push(node->left);//左子节点不为空 就插到总队列中
}
if(node->right){
nodeQueue.push(node->right);
}
}
ans.emplace_back(vector<int>{
levelList.begin(),levelList.end()});
//将当前层的值添加到结果数组中
//前面的vector<int>将队列格式转换格式
isOrderLeft = !isOrderLeft;
}
return ans;
}
};
4.python代码
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
#先层序遍历 再把偶数层的结果翻转即可~
stack = [root]#总队列 遍历的树暂时都装这里
ans = []
while stack:
level = [] #存储每一层用的队列 其结果直接扔到ans结果数组中
for _ in range(len(stack)):
node = stack.pop(0)
if not node:
continue
level.append(node.val)
stack.append(node.left)
stack.append(node.right)
if level:
ans.append(level)
for i in range(1, len(ans), 2):#从1到结果数组的长度 步长为2
ans[i] = ans[i][::-1] #[::-1]是翻转数组的意思
#把ans[i]这个数组翻转过来
return ans
转载：https://blog.csdn.net/qq_45704942/article/details/115859302
查看评论