1、前提(待补充)
1.**DFS（Depth First Search）😗*递归法得到最终的数组（深度优先算法）
其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，如果遇到死路就往回退，回退过程中如果遇到没探索过的支路，就进入该支路继续深入，每个节点只能访问一次。
深度优先搜索应用：先序遍历，中序遍历，后序遍历。二叉树的前序、中序、后序遍历，本质上可以认为是深度优先遍历。是一种回溯思想。
2.BFS（Breadth First Search）:迭代法实现层序遍历，每次遍历二叉树的某一层。
它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现算法。
广度优先搜索应用：层序遍历、最短路径、求二叉树的最大高度、由点到面遍历图、拓扑排序
2、题型
1、广度优先BFS
按照每层队列入队出队的逻辑，依次访问每层元素：
【102】二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。
vector<vector<int>> levelOrder(TreeNode* root){
vector<vector<int>> ret ;
if(!root) return ret;
queue <TreeNode*> q;//定义辅助队列
q.push(root);
while(!q.empty()){
int csize = q.size();//每层的列数
ret.push_back(vector<int>());//ret中添加空的一维数组 创建
for(int i =1;i<=csize;i++){
auto node = q.front();
q.pop();
ret.back().push_back(node->val);
if(node->left)q.push(node->left);//需要更新q,否则第一次 q.pop()以后，q就为空了
if(node->right)q.push(node->right);
}
}
return ret;
}
root = [3,1,4,null,2] 则返回的应该改是{{3}，{1，4}，{2}}
【1302】层数最深叶子节点的和
给你一棵二叉树的根节点 root ，请你返回 层数最深的叶子节点的和 。
解:到ret的最后一层，然后再累加。每一层更新一下sum
【429】N叉树的层序遍历
给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
比二叉树的分支更多了，不止左右子树，所以分组的时候要用for循环去分
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>>ret;//定义返回向量
queue<Node*> q;//定义辅助队列
if(!root)return ret;
q.push(root);//队头push进
while(!q.empty()){
ret.push_back(vector<int>());
int csize = q.size();
for(int i =1;i<=csize;i++){
auto node = q.front();//取队头
q.pop();//弹出队头
ret.back().push_back(node->val);//每次都是在数组尾更新值
//N叉树需要去遍历每个值
for(int j = 0;j< node->children.size();j++){
if(node->children[j])q.push(node->children[j]);
}
}
}
// reverse(ret.begin(), ret.back());
return ret;
}
};
【199】二叉树右视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
这道题还是层序遍历的变形，需要注意的是熟练掌握cize = q.size()是每一层的列数，灵活运用这一特质。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> ret;//定义返回数组
if(!root)return ret;//如果二叉树为空，返回空数组
queue<TreeNode*>q;//定义辅助队列
q.push(root);//将根节点push进队列
while(!q.empty()){
int cize = q.size();//列数(！！)
for(int i = 0;i<cize;i++){
auto node = q.front();
q.pop();
if(i == (cize -1))ret.push_back(node->val);//返回每一层最后
if(node->left)q.push(node->left);
if(node->right)q.push(node->right);
}
}
return ret;
}
};
【637】二叉树的层平均值
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
特别注意：返回如果有精度要求，那么每层和就要设为double 类型。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double> ret;//定义返回数组
if(!root)return ret;
queue<TreeNode*>q;//定义辅助队列
q.push(root);//根结点入队头
while(!q.empty()){
int csize = q.size();//每一层的列数
double sum = 0;//每层和 double类型
for(int i = 0;i< csize;i++){
auto node = q.front();//取队头
q.pop();
sum+=node->val;
if(node->left)q.push(node->left);
if(node->right)q.push(node->right);
}
ret.push_back(sum/csize);//每层求均值
}
return ret;
}
};
【515】找到每行最大值
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
vector<int> ret;//定义返回数组
if(!root)return ret;
queue<TreeNode*> q;//定义辅助队列
q.push(root);//把树根结点推入
vector<vector<int>> aux;//定义辅助一维向量数组
while(!q.empty()){
aux.push_back(vector<int>());
int csize = q.size();//列数
for(int i=0;i<csize;i++){
auto node = q.front();
q.pop();
aux.back().push_back(node->val);
if(node->left)q.push(node->left);
if(node->right)q.push(node->right);;
}
}
//看作一维向量数组
for(auto row:aux){//遍历每行
int max = row[0];//取第一个值作为比较
for(int col:row){
if(col>max){
max = col;
}
}
ret.push_back(max);
}
return ret;
}
};
【103】二叉树的锯齿形层序遍历
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> reverse_level(vector<int> vec){//reverse函数
int vecsize = vec.size();
int temp =0;
for(int i=0;i<vecsize/2;i++){//遍历到中间
temp = vec[vecsize-i-1];
vec[vecsize-i-1] = vec[i];
vec[i] = temp;
}
return vec;
}
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ret;//定义返回的一维数组
if(!root)return ret;
queue<TreeNode*> q;//定义辅助队列
q.push(root);//把root推入q队列
while(!q.empty()){
ret.push_back(vector<int>());//推入一维空数组
int csize = q.size();//列数
for(int i =0;i<csize;i++){
auto node = q.front();
q.pop();
ret.back().push_back(node->val);
if(node->left)q.push(node->left);
if(node->right)q.push(node->right);
}
}
int count_level =0;
for(vector<int> row:ret){
count_level++;//更新层数
if(count_level%2==0){//偶数层
ret[count_level-1] = reverse_level(row);//偶数层颠倒
}
}
return ret;
}
};
2、深度优先DFS
2.1.二叉树的高度和深度
深度：根节点—>该节点 最长边数 +1（前序）
高度：叶节点---->该节点 最长边数 +1（后序）
对于二叉树，深度：根节点到它的叶节点，高度：叶节点到它的根节点。
注意：树的高度和深度都是一样的，但是具体到树的某个节点，深度和高度就是不一样的。
如上图树的高度和深度都是4（看层数=边数+1），节点8 的高度是2 深度是3（都是从1开始的），节点5的高度是4 深度是3。
假设我构造一个二叉树：
5
/ \
2 3
/ \
1 4
我要求他的深度：此时先遍历左子树再遍历右子树：5->2->1 到底返回1，回溯到2再到4 ，返回1，再到2，返回2。5–>3返回1，再到5，返回3和2的最大值 3。
//求二叉树的高度/深度
#include <iostream>
#include <stdio.h>
using namespace std;
struct TreeNode
{
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
int high(TreeNode* node){
if(!node)return 0;
cout<<"node is"<<node->val<<endl;
int h_left = high(node->left);
int h_right=high(node->right);
int res = h_right>h_left ? h_right+1:h_left+1;
cout<<"res is"<<res<<endl;
return res;
}
int main() {
TreeNode* node = new TreeNode(5);
TreeNode* nodel = new TreeNode(2);
TreeNode* noder = new TreeNode(3);
TreeNode* nodell = new TreeNode(1);
TreeNode* nodelr = new TreeNode(4);
node->left = nodel;
node->right =noder;
nodel->left =nodell;
nodel->right=nodelr;
int nodehigh =0;
nodehigh = high(node);
cout<<"final res:"<<nodehigh<<endl;
return 0;
}
【100】验证树是否一致
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
//深度优先搜索
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p==nullptr || q== nullptr)return false;
if(p == nullptr&& q == nullptr)return true;
if(p->val != q->val)return false;
return isSameTree(p->left, q->left)&&isSameTree(p->right, q->right);
}
};
if(p==NULL&&q==NULL) return true;
if(p==NULL||q==NULL) return false;
if(p->val!=q->val) return false;
return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
【108】AVL树
递归
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
由于是升序序列，于是可以选择中间元素作为根节点。
示例1:
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
//如果看成链式结构的话，发现顺序并没有发生变化
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
int len = nums.size();//得到数组长度 每次取mid
return dfs(nums,0,len);
}
TreeNode* dfs(vector<int>& vec,int left,int right){
if(left>=right)return NULL;//注意也不能等于 len = 0 空节点
int mid = (left+right)/2;//得到mid
TreeNode* curr= new TreeNode(vec[mid]);//！新建结点 值
curr->left = dfs(vec,left,mid);//递归 左节点
curr->right = dfs(vec,mid+1,right);//右节点
return curr;
}
};
这道题非常有意思是如何去创建这个新的结点。首先要更新节点值：
TreeNode* curr = new TreeNode(val);//创建一个节点,并且存入值
curr->left = …
curr->right = …
规定左右子树。
【144】前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。前中后序遍历都用递归的方式去实现。
输入：root = [1,null,2,3]
输出：[1,2,3]//返回的是值，所以vector<int>
输入：root = []
输出：[]
输入：root = [1]
输出：[1]
输入：root = [1,null,2]
输出：[1,2]
可以从题解中得出，先序遍历的顺序是NLR，基本上就是输入什么，输出什么，去掉null就好了。特别的，当root为空的时候，应该返回空集。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> vec;//初始化返回向量
traversal(root,vec);
return vec;
}
//回归
void traversal(TreeNode* curr,vector<int>& vec){
if(NULL == curr)return;//如果root为空,则直接返回空向量
//如果root不为空 前序遍历
vec.push_back(curr->val);//中
traversal(curr->left,vec);//左
traversal(curr->right,vec);//右
}
};
用全局变量会加快一点速度
class Solution {
public:
vector<int> vec;//返回节点值 的前序遍历向量
vector<int> preorderTraversal(TreeNode* root) {
traversal(root);
return vec;
}
void traversal(TreeNode* curr){
if(!curr)return;
vec.push_back(curr->val);//返回的是节点值
traversal(curr->left);
traversal(curr->right);
}
};
【94】中序遍历
给你二叉树的根节点 root ，返回它节点值的 中序 遍历。中序遍历LNR，Inorder
输入：root = [1,null,2,3]
输出：[1,3,2]
输入：root = []
输出：[]
输入：root = [1]
输出：[1]
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> vec;//声明返回向量
traversal(root,vec);
return vec;
}
void traversal(TreeNode* root,vector<int> &vec)
{
if(root ==nullptr)return;
traversal(root->left,vec);//L
vec.push_back(root->val);//N
traversal(root->right,vec);//R
}
};
【145】后续遍历
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
输入：root = [1,null,2,3]
输出：[3,2,1]
输入：root = []
输出：[]
输入：root = [1]
输出：[1]
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> vec;//声明返回向量 也可以返回到全局变量去
traversal(root,vec);
return vec;
}
void traversal(TreeNode* root,vector<int> &vec)
{
if(root ==nullptr)return;
traversal(root->left,vec);//L
traversal(root->right,vec);//R
vec.push_back(root->val);//N
}
};
【104】给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
//递归问题
#include<algorithm>
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == nullptr)return 0;//边界条件
return max(maxDepth(root->left),maxDepth(root->right))+1;//非边界条件逻辑
//加一是把当前结点算进去了 比如最后一个叶结点深度是0，但是高度是1
}
};
//其中max函数是包含在algorithm中的
template<class T>
const T& max(const T&a,const T&b)
{
return (a < b)?b:a;
}
树为什么是一种递归问题？
他这个遍历的方式是根结点-左-右，这种常识要记住
maxDepth是怎么运行的：递归
演示网站：Python Tutor code visualizer: Visualize code in Python, JavaScript, C, C++, and Java
递归就是要明白代码的边界条件和非边界条件的逻辑。
计算机怎么执行递归的？栈，最后放进去的结点最先出来，空间复杂度o(n)
【104】二叉树最大深度
输入：root = [3,9,20,null,null,15,7]
输出：3
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
//递归问题
#include<algorithm>
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == nullptr)return 0;//边界条件
return max(maxDepth(root->left),maxDepth(root->right))+1;//非边界条件逻辑
//加一是把当前结点算进去了 比如最后一个叶结点深度是0，但是高度是1
}
};
【559】N叉树的最大深度
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
int maxDepth(Node* root) {
if(root == nullptr)return 0;
int depth = 0;//初始化深度
//int n = root->children.size();
for(int i= 0;i<root->children.size();i++){
depth = max(depth,maxDepth(root->children[i]));//第二层马上跳到第三层
}
return depth + 1;
}
};
用拷贝的形式传入形参
用数组的方式比容器的快
【111】二叉树的最小深度
给定一个二叉树，找出其最小深度。（最小层数）最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
**说明：**叶子节点是指没有子节点的节点。（易错点：当数退化成链表的时候，最小深度不是1，而是从根节点到叶子节点的长度）
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int minDepth(TreeNode* root) {
if(root == nullptr)return 0;
//线性表情况
if(root->left==nullptr && root->right != nullptr)return minDepth(root->right)+1;//这是一个递归
if(root->right==nullptr && root->left != nullptr)return minDepth(root->left)+1;//这是一个递归
//一般情况
return min(minDepth(root->left),minDepth(root->right))+1;
}
};
【543】二叉树的直径
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
总结：做DFS的题都可以把题目往左右子树深度去想
这里的直径 = 左子树深度+右子树深度（不包括根节点）
错误写法：得到的都是0
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
//根节点为root的二叉树的直径 = 左子树的最大深度（不包括根节点）+右子树的最大深度（不包括根节点）
class Solution {
public:
int ans = 0;
int depth(TreeNode* rt){//回溯要单独写
if(!rt)return 0;
int L = depth(rt->left);//左儿子为根的子树深度
int R = depth(rt->right);
ans = max(ans,L+R);//计算diameter（返回每个节点的最大直径）
return max(L,R)+1;//返回节点深度 正常深度应该+1
}
int diameterOfBinaryTree(TreeNode* root) {
depth(root);
return ans;
}
};
![[安洵杯 2019]easy_serialize_php](https://img-blog.csdnimg.cn/img_convert/7c693cd9f6e5ff270c5fa1ccf31c9df7.png)
