建立一棵二叉搜索树二叉搜索树的巨大优势就是：在平均情况下，能够在 O(logN) 的时间内完成搜索和插入元素。递归版本：//插入值为key的结点（递归）TreeNode* insertIntoBST(Tree& t, int key) {if(t == NULL){ //找到插入目标t = new TreeNode;t->val = key;return t;}if(key >

二叉树叶子结点的个数非递归的求法，用广度优先遍历，每出队一个结点，判断它是不是叶子结点。非递归的做法，先由上自下遍历，等遍历到叶子处再逐层返回左右子树的叶子结点总和，最后得到整棵树的叶子结点数。代码如下：#include<iostream>#include<queue>#include<vector>using namespace std;typedef str

判断出栈序列题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。备注：例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。思路，考研中经常出现判断出栈序列是否合理的选择题，这样的题我们就是用入栈序列一边入栈，然后观察出栈序列的首元素，当入栈元素与出栈序列首元素相同

Floyd算法Floyed 算法与 Dijkstra 算法的思想完全一样，遍历整个邻接矩阵，比较每一条边可否加入循环中的两边之间来短接。Floyed 算法基于动态规划算法，可以允许有负权值，但不可以有带负权值的边存在。首先，初始化一个邻接矩阵，初始化一个 dp 矩阵，初始化一个顶点的前趋矩阵prev。#define N 6vector<vector<int> > Graph

后序线索二叉树c++实现

快速排序快速排序有三种写法，平均复杂度几乎相同。我们这里给出最常见的那种，把第一个元素拎出来，然后找到它该去的地方再塞进去。快速排序和冒泡排序都属于交换排序，都属于不稳定排序。一趟快速排序定一个位置，并且把区间分为两部分。int Partition(int* arr,int i,int j){ //j逆向遍历，i正向遍历int temp = arr[i]; //temp存储基准值while(i &

循环队列处理队满和队空的方式顺序存储的队列在队满时再进队出现的溢出往往是假溢出，即还有空间但用不上，为了有效利用队列空间，可将队列元素存放数组首尾相接，形成循环队列。但是构造循环队列时不得不考虑到的问题就是如果不加以限制，队空和队满的情况是相同的。即队头指针和队尾指针的指向相同。一般来说有以下三种解决方式：1、牺牲一个单元来区分队空和队满，也是普遍在利用的方式。队满：（rear + 1）% Que

删除链表中等于给定值val的所有节点备注：链表不带头结点。思路：非递归的解法，需要一个 pre 指针一直指到 val 值结点的上一个结点。但是考虑到链表没有头结点，所以如果首元结点的值为val，就直接头指针后移，然后释放上一个结点就行。递归的解法只需要设置一个指针，遍历完这个结点以后，把后续的任务交给下一层来完成，每一层都在删除完 val 结点后直接把上一层的 next 域改为了 val 值结点的

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a

堆排序前一篇博客中我们列举了对小根堆的相关操作。想把一个数组按照从小到大的顺序来排列，需要用到大根堆。同理，从大到小排序需要小根堆。我们现在试着把一个数组从小到大排序，那么就需要用到大根堆。每次把根与堆的第 len 个元素交换，然后对大小为 len - 1 的堆进行重建堆。不断重复上述过程，直到堆中只剩一个元素。堆排序需要用到向下筛选算法，和重建堆的算法，时间复杂度为 O( N logN )。//