树

计算二叉树的叶子结点数量

//二叉树的结点声明
typedef struct TreeNode {
    int val;    //数据域
    TreeNode *left;     //指向左子树
    TreeNode *right;    //指向右子树
}
 
 
int count = 0;
int getAmount(TreeNode *root){
    travel(root);
    return count;
}
void travel(TreeNode *root){
    if(root==null){
        return;
    }
    if(root->left==null&&root->right==null){
        count++;
    }
    travel(root->left);
    travel(root->right);
}

平衡二叉树的判定

LCR 176. 判断是否为平衡二叉树 - 力扣（LeetCode）

方法一：自顶向下递归时间复杂度：O( $n^{2}$ )

class Solution {
public:
    int height(TreeNode* root) {
        if (root == NULL) {
            return 0;
        } else {
            return max(height(root->left), height(root->right)) + 1;
        }
    }
    bool isBalanced(TreeNode* root) {
     //判断是否为空应放在前面
        if (root == NULL) {
            return true;
        } else {
            return abs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
        }
    }
};

方法二：自底向上的递归时间复杂度：O(n)

思想：类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 −1-1−1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。

	class Solution {
	public:
	    int height(TreeNode* root) {
	        if (root == NULL) {
	            return 0;
	        }
	        int leftHeight = height(root->left);
	        int rightHeight = height(root->right);
	        if (leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1) {
	            return -1;
	        } else {
	            return max(leftHeight, rightHeight) + 1;
	        }
	    }
	    bool isBalanced(TreeNode* root) {
	        return height(root) >= 0;
	    }
	};

二叉树的深度

https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/

方法一：

	class Solution {
	public:
		int max = 0;
	    void trval(TreeNode* root,int depth){
	        if(root == nullptr){
	            return;
	        }
	        //注意用max取最大
	        if(max < depth){
	            max = depth;
	        }
	        trval(root->left,depth+1);
	        trval(root->right,depth+1);
	    }
	    int calculateDepth(TreeNode* root) {
	        trval(root,1);
	        return max;
	    }
	};

方法二：

二叉树的最大深度 = 二叉树的最大高度二叉树的最大高度 = 根结点的高度当前结点的高度 = 左右子树高度的较大值 + 1

class Solution {
public:
    int calculateDepth(TreeNode* root) {
        if(root == nullptr){
            return 0;
        } else {
            int leftHeight = calculateDepth(root->left);
            int rightHeight = calculateDepth(root->right);
            return leftHeight > rightHeight ? leftHeight +1: rightHeight + 1;
        }
    }
};

相同的树

https://leetcode.cn/problems/same-tree/

	class Solution {
	public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == nullptr && q == nullptr){
            return true;
        } else if(p == nullptr || q == nullptr) {
            return false;
        }
        if(p->val == q->val){
            return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
        } else {
            return false;
        }
    }
	};

翻转二叉树

LCR 144. 翻转二叉树 - 力扣（LeetCode）

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(root == NULL){
            return NULL;
        }
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right =temp;
        mirrorTree(root->left);
        mirrorTree(root->right);
        return root;
    }
};

对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

	class Solution {
	public:
	     bool isSymmetric(TreeNode* root) {
		       return trval(root->left,root->right);
		    }
	    bool trval(TreeNode* root1,TreeNode* root2) {
	        if(root1 == nullptr && root2 == nullptr){
	            return true;
	        }
	        if(root1 == nullptr || root2 ==nullptr){
	            return false;
	        }
	        if(root1->val == root2 ->val){
	            return trval(root1->left,root2->right)&&trval(root1->right,root2->left);
	        }
	        else return false;
	    }
	};

合并二叉树

617. 合并二叉树 - 力扣（LeetCode）

class Solution {
public:
   TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
       if(root1 == nullptr && root2 == nullptr){
           return nullptr;
       } else if(root1 == nullptr || root2 == nullptr){
           return root1 == nullptr?root2:root1;
       }
       //建立新节点
       TreeNode *node = new TreeNode;
       node->val = root1->val + root2->val ;
       node->left = mergeTrees(root1->left,root2->left);
       node->right = mergeTrees(root1->right,root2->right);
       
       return node;
       }
};

二叉树的最近公共祖先

236. 二叉树的最近公共祖先 - 力扣（LeetCode）思想：两个节点 p,q 分为两种情况：

p 和 q 在相同子树中
p 和 q 在不同子树中

从根节点遍历，递归向左右子树查询节点信息递归终止条件：如果当前节点为空或等于 p 或 q，则返回当前节点递归遍历左右子树，如果左右子树查到节点都不为空，则表明 p 和 q 分别在左右子树中，因此，当前节点即为最近公共祖先；如果左右子树其中一个不为空，则返回非空节点。

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
	if(!root ||root == p || root == q) return root;
	TreeNode* left = lowestCommonAncestor(root->left,p,q);
	TreeNode* right = lowestCommonAncestor(root->right,p,q);
	if(left&&right) return root;
	return left?left:right;
}

二叉树的中序非递归遍历

二叉树中序遍历非递归算法

94. 二叉树的中序遍历 - 力扣（LeetCode）

void travel(TreeNode *root){
    stack<TreeNode*> s1;
    TreeNode *cur = root;
    while(cur!=null||!s1.empty()){
        while(cur!=null){
            s1.push(cur);
            cur = cur->left;
        }
        cur = s1.top();s1.pop();
        //访问当前顶点cur
        cur = cur->right;
    }
}

二叉树的最大深度

104. 二叉树的最大深度 - 力扣（LeetCode）

//方法一：
int maxDepth(TreeNode* root) {
        stack<TreeNode*>s1;
        stack<int>s2;
        TreeNode* cur = root;
        int curDepth = 1;
        int max=0;
        while(cur != nullptr || !s1.empty()){
            while(cur != nullptr){
                s1.push(cur);
                s2.push(curDepth);
                cur = cur->left;
                //注意遍历左右子树时深度+1
                curDepth++;
            }
            cur = s1.top();
            s1.pop();
            curDepth = s2.top();
            s2.pop();
            if(max<curDepth) max=curDepth;
            cur = cur->right;
            curDepth++;
        }
        return max;
    }
 
//方法二：层次遍历计算二叉树的最大深度
int maxDepth(TreeNode* root) {
	if(!root) return 0;
	int count=0;
	queue<TreeNode*>q;
	q.push(root);
	while(!q.empty()){
		int size = q.size();
		count++;
		for(int i=0;i<size;i++){
			TreeNode* cur = q.front();
			q.pop();
			if(cur->left) q.push(cur->left);
			if(cur->right) q.push(cur->right);
		}
	}
	return count;
}

二叉树的层次遍历

二叉树的层次遍历 102. 二叉树的层序遍历 - 力扣（LeetCode）

void travel(TreeNode *root){
    queue<TreeNode*> q1;
    while(!q1.empty()){
        int cur = q1.front();q1.pop();
        //访问当前顶点
        if(cur->left!=null){
            q1.push(cur->left);
        }
        if(cur->right!=null){
            q1.push(cur->right);
        }
    }
}

哈夫曼树的带权路径长度

//先序递归遍历计算WPL
int wpl = 0;
int getWPL(TreeNode *root,int curLength){
    travel(root,0);
    return wpl;
}
void travel(TreeNode *root,int curLength){
    if(root==null){
        return;
    }
    if(cur->left==null&&cur->right==null){
        wpl += cur->weight * curLength;
    }
    travel(root->left,curLength+1);
    travel(root->right,curLength+1);
}
 
//层次遍历计算二叉树的带权路径长度
int travel(TreeNode *root){
	if(!root) return 0;
    queue<TreeNode*> q1;
    int curLength = 0;
    int wpl = 0;
    q1.push(root);
    while(!q1.empty()){
        int size = q1.size();
        for(int i=0;i<size;i++){
            TreeNode* cur = q1.front();q1.pop();
            if(cur->left==null&&cur->right==null){
                wpl += cur->weight * curLength;
            }
            if(cur->left!=null){
                q1.push(cur->left);
            }
            if(cur->right!=null){
                q1.push(cur->right);
            }
        }
        curLength++;
    }
    return wpl;
}

由先序遍历和中序遍历构造二叉树

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

TreeNode* buildTree(int preorder[],int inorder[]){
    return travel(preorder,inorder,0,preorder.length()-1,0,inorder.length()-1)
}
TreeNode* travel(int preorder[],int inorder[],int pleft,int pright,int ileft,int iright){
    if(pleft>pright||ileft>iright){
        return nullptr;
    }
    TreeNode* node = new TreeNode();
    node->val = preorder[pleft];
    int index = -1;
    for(int i=ileft;i<=iright;i++){
        if(inorder[i]==preorder[pleft]){
            index = i;
            break;
        }
        node->left = travel(preorder,inorder,pleft+1,pleft+index-ileft,ileft,index-1);
        node->right = travel(preorder,inorder,pright-iright+index+1,pright,index+1,iright);
        return node;
    }
}

图

广度优先遍历

· 声明队列并将初始顶点加入队列 · 在队列不为空时,每次出队一个顶点访问,并将该顶点对应的未访问邻接点加入队列 · 循环访问直至队列为空

//模板
void bfs(int matrix[][],int n){
    queue<int> q1;
    int visit[n] = {0};
    q1.push(0);
    visit[0] = 1;
    while(!q1.empty()){
        int cur =  q1.front();q1.pop();
        //对当前结点执行操作
        for(int j=0;j<n;j++){
            if(visit[j]==0&&matrix[cur][j]==1){
                q1.push(j);
                visit[j] = 1;
            }
        }
    }
}

(1)检测图的连通性
(2)计算图的连通分量数量
(3)无权图中计算两点间最短路径

547. 省份数量 - 力扣（LeetCode）

int findCircleNum(vector<vector<int>>& isConnected) {
        int cities = isConnected.size();
        queue<int>q;
        vector<int>visit(cities);
        int provinces = 0;
        for(int i=0;i<cities;i++){
            if(!visit[i]){
                q.push(i);
                visit[i]=1;
                while(!q.empty()){
                    int k = q.front();
                    q.pop();
                    for(int j=0;j<cities;j++){
                        if(isConnected[k][j]&&!visit[j]){
                            q.push(j);
                            visit[j]=1;
                        }
                    }
                }
                provinces++;
            }
        }
        return provinces;
    }

判断图是否为生成树

· 该图为连通图 · 图中边数等于顶点数减一

boolean isTree(int matrix[][],int n){
    queue<int> q1;
    int visit[n] = {0};
    q1.push(0);
    visit[0] = 1;
    int countVertx = 0, countEdge = 0;
    while(!q1.empty()){
        int cur =  q1.front();q1.pop();
        //对当前结点执行操作
        countVertx++;
        for(int j=0;j<n;j++){
            if(matrix[cur][j]==1){
                countEdge++;
                if(visit[j]==0){
                    q1.push(j);
                    visit[j] = 1;
                }
            }
        }
    }
    return countVertx==n && countEdge/2+1==n;
}

//等权值图中计算从顶点s1到顶点s2的最短路径长度
int bfs(int matrix[][],int n,int s1,int s2){
    queue<int> q1;
    int visit[n] = {0};
    q1.push(s1);
    visit[s1] = 1;
    int count = 0;
    while(!q1.empty()){
        int size = q1.size();
        for(int i=0;i<size;i++){
            int cur =  q1.front();q1.pop();
            if(cur==s2){
                return count;
            }
            for(int j=0;j<n;j++){
                if(visit[j]==0&&matrix[cur][j]==1){
                    q1.push(j);
                    visit[j] = 1;
                }
            }
        }
        count++;
    }
}

深度优先遍历

· 从当前顶点开始访问,选择一个未访问邻接点进行递归访问 · 直至没有可以选择的未访问邻接点,返回上一层试探其他可能

void dfs(int matrix[][],int n){
    int visit[n] = {0};
    travel(matrix,n,visit,0);
}
void travel(int matrix[][],int n,int visit,int i){
    if(visit[i]==1){
        return;
    }
    //访问当前顶点
    visit[i] = 1;
    for(int j=0;j<n;j++){
        if(matrix[i][j]==1){
            travel(matrix,n,visit,j);
        }
    }
}

(1)检测图的连通性
(2)计算图的连通分量数量
(3)列举从顶点s1到顶点s2的所有可能路径

vector<int> path;
void dfs(int matrix[][],int n,int s1,int s2){
    int visit[n] = {0};
    travel(matrix,n,visit,s1,s2);
}
void travel(int matrix[][],int n,int visit,int i,int k){
    if(visit[i]==1){
        return;
    }
    if(i==k){
        cout<<path<<k<<endl;
        return;
    }
    path.push_back(i);
    visit[i] = 1;
    for(int j=0;j<n;j++){
        if(matrix[i][j]==1){
            travel(matrix,n,visit,j,k);
        }
    }
    path.remove();
    visit[i] = 0;
}

695. 岛屿的最大面积 - 力扣（LeetCode）

int dx[4]={1,0,-1,0};
    int dy[4]={0,1,0,-1};
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int n=grid.size();
        int m=grid[0].size();
        vector<vector<int>> visit(n,vector<int>(m));
        int maxArea = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]==1&&visit[i][j]==0){
                    int curArea=dfs(grid,n,m,visit,i,j);
                    if(maxArea<curArea){
                        maxArea = curArea;
                    }
                }
            }
        }
        return maxArea;
    }
    int dfs(vector<vector<int>>& matrix,int n,int m,vector<vector<int>>& visit,int x,int y){
        if(x<0||x>=n||y<0||y>=m||visit[x][y]==1||matrix[x][y]==0){
            return 0;
        }
        visit[x][y]=1;
        int count = 1;
        for(int i=0;i<4;i++){
                count += dfs(matrix,n,m,visit,x+dx[i],y+dy[i]);
            }
        return count;
    }

图的应用

Dijkstra算法

朴素版Dijkstra算法 · 可求出图中一个目标点到其他所有顶点的最短路径长度 · 仅适用于不存在负权值边的有向图中 · 时间复杂度为 $O (n^{2})$ ·在未确定最短距离点中寻找距离最近的点，以此点更新其他点的距离

int[] Dijkstra(int matrix[][],int n,int tar){
	int dist[n] = {INT.MAX_VALUE};
	int visit[n] = {0};
	dist[tar] = 0;   //tar目标点
	visit[tar] = 1;
	for(int i=1;i<n;i++){
		int mid = -1; //不在当前已经确定最短距离的点中的，距离最近的点
		int min = INT.MAX_VALUE;
		for(int j=0;j<n;j++){
			if(visit[j]==0 && matrix[tar][j]<min){
				mid = j;
				min = matrix[tar][j];
			}
		}
		dist[mid] = min;
		visit[mid] = 1;
		//用mid更新其他点的距离
		for(int k=0;k<n;k++){
			if(visit[k]==0&&matrix[tar][k]>matrix[tar][mid]+matrix[mid][k]){
				matrix[tar][k] = matrix[tar][mid]+matrix[mid][k];
			}
		}
	}
	return dist[];
}

Floyd算法

· 可求出图中任意两个顶点间的最短路径长度 ·不适用于环中权值和为负数的有向带权图 ·时间复杂度为 $O (n^{3})$ ·逐步尝试在原路径中加入顶点k做中间点，以此中间点更新顶点i到j的距离(i→k→j)

//假设k为中转点,i为起点,j为终点
int[][] Floyd(int matrix[][],int n){
	for(int k=0;k<n;k++){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(matrix[i][j]>matrix[i][k]+matrix[k][j]){
					matrix[i][j] = matrix[i][k] + matrix[k][j];
				}
			}
		}
	}
	return matrix;
}

743. 网络延迟时间 - 力扣（LeetCode）

int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        const int inf = INT_MAX / 2;
        vector<int>dist(n,inf);
        vector<int> visit(n);
        vector<vector<int>>matrix(n,vector<int>(n,inf));
        for(auto &t : times){
            int x = t[0] - 1;
            int y = t[1] - 1;
            matrix[x][y] = t[2];
        }
        k--;    //使结点编号位于[0，n-1],k为目标结点
        dist[k]=0;
        visit[k]=1;
        for(int i=0;i<n;i++){
            int mid = -1;
            int min = inf;
            //在当下情况下，已经确定的点之外距离最近的结点mid
            for(int j=0;j<n;j++){
            //visit[j]==0已保证该点不为k-1
                if(min > matrix[k][j]&&visit[j]==0){
                    mid = j;
                    min = matrix[k][j];
                }
            }
            if(mid==-1) break;  //孤立点
            dist[mid] = min;
            visit[mid]=1;
            //以mid为中转点更新距离
            for(int x=0;x<n;x++){
                if(visit[x]==0&&matrix[k][x]>matrix[k][mid]+matrix[mid][x]){
                    matrix[k][x]=matrix[k][mid]+matrix[mid][x];
                }
            }
        }
        //dist[]内最大值
        int ans = 0;
        for(int i=0;i<n;i++){
            if(ans<dist[i]) ans = dist[i];
        }
        return ans==inf?-1:ans;
    }

2021年最后一题

int roads[][] = [[0,1,5],[0,2,7],[0,3,9],[1,0,5],...];
 
int getVillage(int roads[][],int n){
	int matrix[n][n] = {INT.MAX_VALUE};
	//对二维数组roads进行一次强循环遍历
	for(int edge[]:road){
		//edge表示一条有向带权边
		//edge[0]表示起点,edge[1]表示终点,edge[2]表示权值
		matrix[edge[0]][edge[1]] = edge[2];
	}
	for(int k=0;k<n;k++){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(matrix[i][j]>matrix[i][k]+matrix[k][j]){
					matrix[i][j] = matrix[i][k] + matrix[k][j];
				}
			}
		}
	}
	int min = INT.MAX_VALUE;
	int village = -1;
	for(int j=0;j<n;j++){
		int sum = 0;
		for(int i=0;i<n;i++){
			sum += matrix[i][j];
		}
		if(sum<min){
			min = sum;
			village = j;
		}
	}
	return village;
}

拓扑排序

·判断图中是否存在环 ·采用邻接表 $O (∣ V ∣ + ∣ E ∣)$ ,采用邻接矩阵 $O (∣ V ∣^{2})$ ·思想： 1.选择入度为0的顶点并输出 2.删除该顶点和所有以它为起点的有向边 3.重复1、2直至为空或不存在入度为0的点为止(有环)

void tpSort(int matrix[][],int n){
	int inDegree[n] = {0};
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(matrix[i][j]==1){
				inDegree[j]++;
			}
		}
	}
	queue<int> q1;
	for(int i=0;i<n;i++){
		if(inDegree[i]==0){
			q1.push(i);
		}
	}
	while(!q1.empty()){
		int cur = q1.front();q1.pop();
		//访问当前顶点cur
		for(int j=0;j<n;j++){
			if(matrix[cur][j]==1){
				inDegree[j]--;
				if(inDegree[j]==0){
					q1.push(j);
				}
			}
		}
	}
}

207. 课程表 - 力扣（LeetCode）

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int>inDegree;
        vector<vector<int>>edges;
        int count = 0;
        inDegree.resize(numCourses);
        edges.resize(numCourses);
        for(const auto& info:prerequisites){
            edges[info[1]].push_back(info[0]);
            inDegree[info[0]]++;
        }
        queue<int> q;
        for(int i=0;i<numCourses;i++){
            if(inDegree[i]==0){
                q.push(i);
            }
        }
        while(!q.empty()){
            int cur = q.front();
            q.pop();
            count++;
            for(int i:edges[cur]){
                inDegree[i]--;
                if(inDegree[i]==0){
                    q.push(i);
                }
            }
        }
       return count == numCourses; 
    }

802. 找到最终的安全状态 - 力扣（LeetCode）

vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n=graph.size();
        vector<int> res;
        vector<vector<int>> edges(n);
        vector<int>outDegree(n);
        for(int i=0;i<n;i++){
            for(int j:graph[i]){
                edges[j].push_back(i);
            }
            outDegree[i] = graph[i].size();
        }
        queue<int> q;
        for(int i=0;i<n;i++){
            if(outDegree[i]==0){
                q.push(i);              
            }
        } 
        while(!q.empty()){
            int cur = q.front();
            q.pop();
            for(int i:edges[cur]){
                outDegree[i]--;
                if(outDegree[i]==0){
                    q.push(i);
                }
            }
        }
        for(int i=0;i<n;i++){
            if(outDegree[i]==0) res.push_back(i);
        }
        return res;
    }

查找

二分查找(折半查找)

·适用于顺序存储的有序表 ·时间复杂度： $O (l o g_{2} n)$ 704. 二分查找 - 力扣（LeetCode）

int search(vector<int>& nums, int target) {
        int low = 0;
        int n = nums.size();
        int high = n-1;
        while(low<=high){
            int mid = (low - high)/2 + high;
            if(nums[mid] < target){
                low = mid + 1;
            }else if(nums[mid] > target){
                high = mid - 1;
            }else {
                return mid;
            }
        }
        return -1;
    }
//递归实现
int binaty_serch(vector<int>& nums,int low,int high,int target){
	if(low>high) return -1;//注意
	int mid = (low - high)/2 + high;
	if(nums[mid] > target){
		return binaty_serch(nums,low,mid-1,target);
	}else if(nums[mid] < target){
		return binaty_serch(nums,mid+1,high,target);
	}else return mid;
}

35. 搜索插入位置 - 力扣（LeetCode）

int searchInsert(vector<int>& nums, int target) {
        int low = 0;
        int high = nums.size() - 1;
        while(low <= high){
            int mid = (low - high) / 2 + high;
            if(nums[mid] < target){
                low = mid + 1;
            }else if(nums[mid] > target){
                high = mid - 1;
            }else return mid;
        }
        return low;
    }

278. 第一个错误的版本 - 力扣（LeetCode）

int firstBadVersion(int n) {
       int low = 1;
       int high = n;
       while(low <= high){//循环至左右端点相同
           int mid = (low - high)/2 + high;
           if(isBadVersion(mid)){
               high = mid - 1;
           }else{
               low = mid + 1;
           }
       }
       return low;
    }

74. 搜索二维矩阵 - 力扣（LeetCode）

bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int low = 0, high = m * n - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int x = matrix[mid / n][mid % n];
            if (x < target) {
                low = mid + 1;
            } else if (x > target) {
                high = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }

153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

int findMin(vector<int>& nums) {
	int low = 0;
	int high = nums.size()-1;
	while(low < high){
		int mid = (high - low)/2 + low;
		if(nums[mid] < nums[high]){
			high = mid;
		}else {
			low = mid + 1;
		}
	}
	return nums[low];
}

二叉搜索树

二叉搜索树的查找

· 左子树上所有结点关键字均小于当前结点 · 右子树上所有结点关键字均大于当前结点时间复杂度为 $O (l o g_{2} n)$ ~ $O (n)$ 700. 二叉搜索树中的搜索 - 力扣（LeetCode）

TreeNode* search(TreeNode *root,int target){
	if(root==null){
		return null;
	}
	if(root->val<target){
		return search(root->right,target);
	} else if(root->val>target){
		return search(root->left,target);
	} else {
		return root;
	}

二叉搜索树的插入

时间复杂度为 $O (l o g_{2} n)$ ~ $O (n)$ 701. 二叉搜索树中的插入操作 - 力扣（LeetCode）

TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root==nullptr){
            TreeNode* node = new TreeNode();
            node->val = val;
            return node;
        }
        if(root->val < val){
            root->right = insertIntoBST(root->right,val);
        }
        if(root->val > val){
            root->left = insertIntoBST(root->left,val);
        }
        return root;
    }

二叉搜索树的构造

时间复杂度为 $O (n l o g_{2} n)$ ~ $O (n^{2})$

TreeNode* create(int nums[],int n){
	TreeNode *root = null;
	for(int i=0;i<n;i++){
		root = insert(root,nums[i]);
	}
}

二叉搜索树的删除

· 被删除结点为叶子结点,直接删除即可 · 被删除结点有一个孩子,直接让孩子结点顶替即可 · 被删除结点有两个孩子,则让中序序列的前驱/后继结点进行值取代,进而递归删除该前驱/后继结点 ·时间复杂度为 $O (l o g 2 n)$ ~ $O (n)$ 450. 删除二叉搜索树中的节点 - 力扣（LeetCode）

TreeNode* deleteNode(TreeNode *root,int key){
	if(root==nullptr){
		return nullptr;
	} 
    if(root->val<key){
		root->right = deleteNode(root->right,key);
	}
    if(root->val>key){
		root->left = deleteNode(root->left,key);
	}
     if (root->val == key) {
        // 被删除结点为叶子结点,直接删除即可
        if(root->left==nullptr&&root->right==nullptr){
            return nullptr;
        // 被删除结点有一个孩子,直接让孩子结点顶替即可
        } else if(root->left==nullptr||root->right==nullptr){
            return root->left==nullptr?root->right:root->left;
        // 被删除结点有两个孩子,则让中序序列的后继结点
        // 进行值取代,进而递归删除该后继结点
        } else {
            TreeNode *cur = root->right;
            while(cur->left!=nullptr){
                cur = cur->left;
            }
            root->val = cur->val;
            root->right = deleteNode(root->right,cur->val);
        }
     }
	return root;
}

98. 验证二叉搜索树 - 力扣（LeetCode）

如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。
时间复杂度：O(n)

//方法一：递归
bool helper(TreeNode* root,long long lower,long long upper){
        if(root == nullptr) return true;
        if(root->val <= lower || root->val >= upper){
            return false;
        }
        return helper(root->left,lower,root->val) && helper(root->right,root->val,upper);
    }
bool isValidBST(TreeNode* root) {  
    return helper(root,LONG_MIN,LONG_MAX);   
}
方法二：中序遍历
bool isValidBST(TreeNode* root) {
        stack<TreeNode*>s;
        //保存当前节点中中序前驱的值，初值为-∞
        long long inorder = (long long)INT_MIN - 1; 
        while(!s.empty()||root != nullptr){
            while(root){
                s.push(root);
                root = root->left;
            }
            root = s.top();
            s.pop();
            //如果中序遍历得到的结点的值小于等于前一个 inorder,说明不是二叉搜索树
            if(root->val > inorder){
                inorder = root->val;
                root = root->right;
            }
            else return false;
        }
        return true;   
    }

指定结点在给定二叉排序树中的层次查找该结点所用的次数就是该结点在二叉排序树中的层次

int level(TreeNode* p,TreeNode* bt){
    int n = 0;   //统计查找次数
    TreeNode* cur = bt;
    if(bt != null){
        n++;
        while(cur->val != p->val){
            if(cur->val < p->val)
                cur = cur->right; //在右子树中查找
            else 
                cur = cur->left; //在左子树中查找
            n++;                 //层次加1
        } 
    }
    return n;
}

从大到小输出二叉排序树中所有值不小于k的关键字

void travel(TreeNode* root,int target){
    if(root == null) return ;
    if(root->right) travel(root->right,target); //递归输出右子树结点
    if(root->val >= target) cout<<root->val;    //只输出大于或等于k的结点值
    if(root->left) travel(root->left,target);   //递归输出左子树结点
}

1. 两数之和 - 力扣（LeetCode）

vector<int> twoSum(vector<int>& nums, int target) {
	unordered_map<int, int> hashtable;
	for (int i = 0; i < nums.size(); ++i) {
		auto it = hashtable.find(target - nums[i]);
		if (it != hashtable.end()) {
			return {it->second, i};
		}
		hashtable[nums[i]] = i;
	}
	return {};
}

散列表 1512. 好数对的数目 - 力扣（LeetCode）

int numIdenticalPairs(int* nums, int numsSize) {
    int hash[256];
    int sum = 0;
    memset(hash, 0, sizeof(hash));
    for(int j = 0; j < numsSize; j++)
    {
        sum += hash[nums[j]];
        ++hash[nums[j]];
    }
    return sum;
}

排序

插入排序

·基本思想：每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成。 ·直接插入排序 ·思想： $(1)$ 找出 $L (i)$ 在 $L [1... i - 1]$ 中的插入位置 $k$ $(2)$ 将 $L [k ... i - 1]$ 中的所有元素依次后移一个位置 $(3)$ 将 $L (i)$ 复制到 $L (k)$ · 在数组相对有序时时间复杂度较好 · 适用于小规模排序过程 ·时间复杂度：最好 $O (n)$ 最坏 $O (n^{2})$ ·空间复杂度： $O (1)$ ·稳定

//链表实现直接插入排序
//dummy ：有序
//cur:无序
ListNode* insertSort(ListNode *head){
	ListNode *dummy = new ListNode();
	dummy->next = head;
	ListNode *cur = head->next;
	head->next = null;
	while(cur!=null){
		ListNode *p = dummy; 
		ListNode *q = dummy->next;
		//寻找插入位置
		while(q!=null&&q->val<=cur->val){
			p = p->next;
			q = q->next;
		}
		//执行插入操作 p和q之间
		ListNode *temp = cur->next;//保存当前结点的下一个结点
		p->next = cur;
		cur->next = q;
		cur = temp; 
	}
	return dummy->next;
}

折半插入排序

相比于直接插入排序,元素之间的比较次数更少
仅减少比较次数约为 $O (n l o g_{2} n)$ ,元素移动次数未变，时间复杂度仍为 $O (n^{2})$
稳定

希尔排序

时间复杂度取决于增量序列,组内采用直接插入排序
常用于预排序过程
时间复杂度: $O (n^{1.3})$ 最坏 $O (n^{2})$
空间复杂度： $O (1)$
不稳定

交换排序

思想：根据序列中两个元素的关键字的比较结果来对换这两个记录在序列中的位置

冒泡排序

在数组有序时可提前结束排序过程
思想
- 从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即 $A [i - 1] > A [i]$ )，则交换它们，直到序列比较完
- 每趟冒泡的结果是把序列中的最小元素（或最大元素）放到序列的最终的位置
- 最多做 n-1 趟冒泡
时间复杂度：最好 $O (n)$ 最坏 $O (n^{2})$ 平均 $O (n^{2})$
空间复杂度： $O (1)$
稳定

//从后向前的冒泡排序
void bubbleSort(int nums[],int n){
	for(int i=1;i<n;i++){  //n-1趟
		boolean flag = true;  //表示本趟冒泡是否发生交换的标志
		for(int j=n-1;j>=i;j--){
			if(nums[j]<nums[j-1]){  //若为逆序
				//交换
				int temp = nums[j];
				nums[j] = nums[j-1];
				nums[j-1] = temp;
				flag = false;
			}
		}
		if(flag) break; //若本趟遍历后没有发生交换，说明已经有序
	}
}
//从前向后的冒泡排序
void bubbleSort(int nums[],int n){
	for(int i=1;i<n;i++){
		boolean flag = true;
		for(int j=0;j<n-i;j++){
			if(nums[j]>nums[j+1]){
				int temp = nums[j];
				nums[j] = nums[j+1];
				nums[j+1] = temp;
				flag = false;
			}
		}
		if(flag){
			break;
		}
	}
}
//双向冒泡
void bubbleSort(int nums[],int n){
	int low = 0, high = n-1;
	while(low<high){
		for(int j=low;j<high;j++){
			if(nums[j]>nums[j+1]){
				int temp = nums[j];
				nums[j] = nums[j+1];
				nums[j+1] = temp;
			}
		}
		high--;
		for(int j=high;j>low;j--){
			if(nums[j]<nums[j-1]){
				int temp = nums[j];
				nums[j] = nums[j-1];
				nums[j-1] = temp;
			}
		}
		low++;
	}
}

快速排序

在数组升序/降序时,时间复杂度最差
是所有内部排序算法中平均性能最佳的排序算法
适用于中等规模排序过程
思想：（基于分治法）
在待排序表 $L [1... n]$ 中任取一个元素pivot作为枢轴（通常取首元素）
通过一次划分后，pivot放在最终的位置 $L (k)$ ,其中 $L [1... k - 1]$ 均小于pivot, $L [k + 1... n]$ 均大于或等于pivot
递归地对两个子表重复上述过程，直至每部分只有一个元素或为空为止
时间复杂度：最坏 $O (n^{2})$ 最理想 $O (n l o g_{2} n)$ ——平均
空间复杂度：最好 $O (l o g_{2} n)$ 最坏 $O (n)$ 平均 $O (l o g_{2} n)$
不稳定

//快速排序
void quickSort(int nums[],int low,int high){
	if(low>=high){
		return;
	}
	int pivotpos = partition(nums,low,high);
	quickSort(nums,low,pivotpos-1);
	quickSort(nums,pivotpos+1,high);
}
	//划分函数,选定枢轴值后将数组分为大于枢轴值和小于枢轴值两部分
int partition(int nums[],int low,int high){
	int pivot = nums[low];
	//low （== high）之前的元素均小于privot,之后的元素均大于或等于privot
 
    //privot 的最终位置为 low 所指的位置
	while(low<high){
	//high往前找，找到第一个小于privot的元素交换到low
		while(low<high&&nums[high]>=pivot){
			high--;
		}
		nums[low] = nums[high];
		//low往后找，找到第一个大于privot的元素交换到high
		while(low<high&&nums[low]<=pivot){
			low++;
		}
		nums[high] = nums[low];
	}
	nums[low] = pivot;
	return low;
}
 
	(1)划分0/1序列
	int partition(int nums[],int low,int high){
		int pivot = nums[low];
		while(low<high){
			while(low<high&&nums[high]>=pivot){
				high--;
			}
			nums[low] = nums[high];
			while(low<high&&nums[low]<=pivot){
				low++;
			}
			nums[high] = nums[low];
		}
		nums[low] = pivot;
		return low;
	}
 
	(2)划分奇偶序列
	int partition(int nums[],int low,int high){
		int pivot = nums[low];
		while(low<high){
			while(low<high&&nums[high]%2==0){
				high--;
			}
			nums[low] = nums[high];
			while(low<high&&nums[low]%2==1){
				low++;
			}
			nums[high] = nums[low];
		}
		nums[low] = pivot;
		return low;
	}
	(3)快速选择算法
	不在意数组是否整体有序,只获取特定位置元素值
	时间复杂度为O(n)
	void quickSelect(int nums[],int low,int high,int target){
		if(low>=high){
			return;
		}
		int pivotpos = partition(nums,low,high);
		if(pivotpos==target){
			return;
		} else if(pivotpos<target){
			quickSelect(nums,pivotpos+1,high);
		} else {
			quickSelect(nums,low,pivotpos-1);
		}
	}

选择排序

思想：
每一趟（如第i趟）在后面n-i+1(i=1，2，···，n-1)个待排序元素中选取关键字最小的元素，作为有序子序列中的第i个元素，直到做完第i-1趟
简单选择排序
时间复杂度： $O (n^{2})$
空间复杂度： $O (1)$
不稳定（第i趟选出关键字最小的元素与 $L (i)$ 交换，可能导致第i个元素与其含有相同关键字元素的相对位置发生变化

堆排序

适合关键字较多的情况
堆的判定：
```
  $(1<=i<=(n/2)_{向下取整})$
```

  $1.L(i) >= L(2i) 且 L(i) >= L(2i+1)$

  大根堆  任意一个非根结点的值小于等于其双亲结点的值

  $2.L(i) <= L(2i) 且 L(i) <= L(2i+1)$

  小根堆    根节点是最小元素

堆的构建：在建含n个元素的堆时，关键字的比较总次数不超过4n,时间复杂度 $O (n)$ ;调整与树高有关 $O (h)$
堆的插入
堆的删除
时间复杂度： $O (n l o g_{2} n)$
空间复杂度： $O (1)$
不稳定

二路归并排序

适用于大规模排序过程
基于分治法,通过递归实现
思想：
将两个或两个以上的有序表合成新的有序表
假定待排序表含有n个记录，则可视为n个有序的子表，然后两两合并······合并为长度为n的有序表
时间复杂度：每趟 $O (n)$ ,共需 $[O (l o g_{2} n)]^{向上取整}$ 趟归并故为 $O (n l o g_{2} n)$
空间复杂度： $O (n)$
稳定

void mergeSort(int nums[],int low,int high){
	if(low>=high){
		return;
	}
	int mid = (low+high)/2;
	mergeSort(nums,low,mid);
	mergeSort(nums,mid+1,high);
	merge(nums,low,mid,high);
}
void merge(int nums[],int low,int mid,int high){
	int temp[];
	for(int i=low;i<=high;i++){
		temp[i] = nums[i];
	}
	int i = low, j = mid+1, k = low;
	while(i<=mid&&j<=high){
		if(temp[i]<=temp[j]){
			nums[k++] = temp[i++];
		} else {
			nums[k++] = temp[j++];
		}
	}
	while(i<=mid){
		nums[k++] = temp[i++];
	}
	while(j<=high){
		nums[k++] = temp[j++];
	}
}
 
	(1)链表实现归并排序
	ListNode* mergeSort(ListNode *head){
		if(head==null||head->next==null){
			return head;
		}
		ListNode *mid = getMid(head);
		ListNode *left = mergeSort(head);
		ListNode *right = mergeSort(mid);
		return merge(left,right);
	}
	ListNode* merge(ListNode *list1,ListNode *list2){
		ListNode *dummy = new ListNode();
		ListNode *tail = dummy;
		while(list1!=null && list2!=null){
			if(list1->val <= list2->val){
				tail->next = list1;
				list1 = list1->next;
			} else {
				tail->next = list2;
				list2 = list2->next;
			}
			tail = tail->next;
		}
		tail->next = list1==null?list2:list1;
		return dummy->next;
	}
	ListNode* getMid(ListNode *head){
		ListNode *slow = head;
		ListNode *fast = head;
		ListNode *pre = null;
		while(fast!=null&&fast->next!=null){
			fast = fast->next->next;
			pre = slow;
			slow = slow->next;
		}
		pre->next = null;
		return slow;
	}

基数排序

排序过程不涉及元素之间的比较
空间复杂度： $O (r)$
时间复杂度：d趟分配和收集，一趟分配 $O (n)$ ,一趟收集 $O (r)$ 故 $O (d (n + r))$ 与初始状态无关
稳定

🪴 Edwin Aze's Blog

最近文章

洛师薅羊毛教程

挖土机编程 CSP-J 2022 模拟赛 Round 2

我是学生 如何白嫖GPT4

最近笔记

Hi~

202503051617 latex documentclass options

代码模板

树