图的存储方式
1、邻接矩阵（二维数组）
//邻接矩阵构建图
#include "stdafx.h"
#include<iostream>
#include<vector>
using namespace std;
void Creat_graph(vector<int>&nums, vector<vector<int> >& container, int n, int e) {
//一个存储临时变量的小工具
int k = 0;
//图里面是5个顶点，8条边
cout << "请输入顶点个数" << endl;
cin >> n;
cout << "请输入边数" << endl;
cin >> e;
//给顶点数组赋初值
for (int i = 0; i < n; i++) {
cin >> k;
nums.push_back(k);
}
//初始化用于存储边信息的二维数组
for (int i = 0; i < n; i++) {
//每次都重新创建一个新的temp
vector<int>temp;
for (int j = 0; j < n; j++) {
cin >> k;
temp.push_back(k);
}
container.push_back(temp);
}
}
int main()
{
vector<int> nums;
vector<vector<int> > container;
//初始化定点数、边数为0
int n = 0, e = 0;
//无向图
Creat_graph(nums, container, n, e);
return 0;
}
2、邻接表
无向图示例
有向图示例
（代码未完成，先刷题，代码以后补）
二叉查找树——面试题多是中等偏容易的难度
概念
STL中的set或者map就是利用二叉查找树来实现的，不过是一个平衡的二叉查找树。
插入节点
平衡树是绝对平衡，红黑树不是完美的平衡树，它的高度差并不是所有的节点都小于等于1。
avl、线段树就是完美的平衡二叉树。
递归实现插入节点
循环实现插入节点
二叉查找树查找数值
递归实现查找
循环实现查找
二叉树的节点删除
后继节点就是中序遍历中，遍历完目标节点之后要遍历的那个节点。
LeetCode 108
/*
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。
*/
#include "stdafx.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
//二叉查找树的插入过程
void BST_insert(TreeNode* node, TreeNode* insert_node) {
while (node != insert_node) {
//如果该点的值小于根节点的值，将该节点插入根节点的左子树
if (insert_node->val < node->val) {
//如果左子树为空
if (!node->left) {
//该点便是左孩子
node->left = insert_node;
}
//更新左孩子为根节点
node = node->left;
}
//如果该点的值大于根节点的值，将该节点插入根节点的右子树
else {
//如果右子树为空
if (!node->right) {
node->right = insert_node;
}
//更新右孩子为根节点
node = node->right;
}
}
}
//递归，每次都把每段的中值作为根节点
void helper(vector<TreeNode*>&answer, int begin, int end,vector<int> nums) {
if (begin > end) return;
int middle = (begin + end) / 2;
answer.push_back(new TreeNode(nums[middle]));
helper(answer, begin, middle-1, nums);
helper(answer, middle + 1, end, nums);
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
int length = nums.size();
int begin = 0, end = length, middle = 0;
//如果nums为空，则返回空
if (!length) return nullptr;
vector<TreeNode*>answer;
//排序
sort(nums.begin(), nums.end());
//递归构造树，每次都选取每段的中间值
helper(answer, 0, length - 1, nums);
//将获取的数组用于构造二叉查找树
for (size_t i = 0; i < answer.size(); i++) {
BST_insert(answer[0], answer[i]);
}
return answer[0];
}
int main()
{
vector<int> nums = { -10,-3,0,5,9 };
sortedArrayToBST(nums);
return 0;
}
LeetCode 450
二叉查找树的节点删除，若找到，删除该节点并返回更新后的根节点，若没找到，返回原树的根节点。
待删除的节点会出现四种情况：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
//查找值为value的节点的父节点的位置
TreeNode* BET_search(TreeNode* node,int value, TreeNode*&parent){
while(node){
//找到了
if(node->val==value){
break;
}
//没找到，则将该节点的值赋值给parent
parent=node;
//如果value的值小于node的值
if(value<node->val){
//查找node左子树
node=node->left;
//否则
}else{
//查找node右子树
node=node->right;
}
}
return node;
}
//node最多一个子节点
//（此时的node是传入的后继节点的位置，后继节点最多有一个右孩子，或者node是最多一个孩子节点的且父节点不为空的节点）
void delete_node(TreeNode* parent, TreeNode *node){
//node的值小于parent的值，则node是parent的左孩子
if(node->val<parent->val){
//若node只存在左孩子
if(node->left && !node->right){
//左孩子成为parent的左孩子
parent->left=node->left;
}
//若node只存在右孩子
else if(!node->left && node->right){
//右孩子成为parent的左孩子
parent->left=node->right;
//node是叶结点
}else{
//直接删除
parent->left=NULL;
}
}
else if(node->val>parent->val){
if(node->left && !node->right){
parent->right=node->left;
}
else if(!node->left && node->right){
parent->right = node->right;
}else{
parent->right=NULL;
}
}
}
//找后继节点，后继节点最多有一个右孩子，他是查找的节点的右孩子中值最小的那个节点
TreeNode* find_successor(TreeNode* node, TreeNode* &parent){
parent = node;
TreeNode *ptr = node ->right;
//如果存在左孩子，就一直向下找
while(ptr->left){
parent=ptr;
ptr=ptr->left;
}
return ptr;
}
TreeNode* deleteNode(TreeNode* root, int key) {
//如果传入的树为空，返回空
if(!root) return nullptr;
TreeNode* parent = NULL;
//查找值为key的node节点，存在则返回该节点的位置，不存在则返回空
TreeNode* node = BET_search(root, key, parent);
//如果返回空，证明不存在值为key的节点
if(!node) return root;
//如果node节点有两个子节点
if(node->left && node->right){
//查找node的后继节点
TreeNode* successor = find_successor(node, parent);
//删除后继节点
delete_node(parent, successor);
//将后继节点赋值给node
node->val = successor->val;
return root;
}
//如果node节点为叶结点或者只有一个孩子节点且父节点不为空时
//此时node肯定不是根节点
if(parent){
//删除该节点
delete_node(parent, node);
return root;
}
//当该节点只有左孩子且没有父节点时，该节点是只有左孩子的根节点
if(node->left){
root=node->left;
}
//当该节点只有右孩子且没有父节点时，该节点是只有右孩子的根节点
else{
root=node->right;
}
return root;
}
};LeetCode 538
思路：首先要找到最右的节点，反中序遍历的累加。
//反中序遍历
void travel_tree(TreeNode* root, int &sum){
if(!node) return;
travel_tree(root->right, sum);
sum+=node->val;
travel_tree(root->left, sum);
}
TreeNode* convertBST(TreeNode* root) {
int sum=0;
travel_tree(root, sum);
return root;
}LeetCode 207
题目有点类似于判断给定的课程是否能够拓扑排序，也就是不出现环。对于判断一个图是否有环，有两种解法，深度优先和广度优先
深度优先解法：
void makeGraph(vector<unordered_set<int>>& graph, vector<pair<int, int>>& prerequisites) {
for (auto p : prerequisites)
//如果想学first表示的课程，需要先学习second表示的课程
//构建hash键值对
graph[p.second].insert(p.first);
}
//深度优先
bool dfs(vector<unordered_set<int>>& graph, int neighbor, vector<bool>& visited, vector<bool>& onPath) {
//如果被访问过，则返回false
if (visited[neighbor]) return false;
//标记访问的该节点
visited[neighbor] = onPath[neighbor] = true;
//获取该hash键所指所有的值
for (int n : graph[neighbor])
//说明存在环
if (onPath[n] || dfs(graph, n, visited, onPath))
return true;
onPath[neighbor] = false;
return false;
}
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
//初始化空间大小为numCourses，存入unordered_set中
vector<unordered_set<int>> graph(numCourses);
//将输入的东西赋值给unordered_set
makeGraph(graph, prerequisites);
//visited用于存储是否访问过，onPath用于存储
vector<bool> visited(numCourses, false), onPath(numCourses, false);
for (int i = 0; i < numCourses; i++) {
//如果该节点访问过，跳出循环
if (visited[i]) continue;
//如果存在环
if (dfs(graph, i, visited, onPath))
return false;
}
return true;
}广度优先解法：
void makeGraph(vector<unordered_set<int>>& graph, vector<pair<int, int>>& prerequisites) {
for (auto p : prerequisites)
graph[p.second].insert(p.first);
}
void getDegrees(vector<int>& degrees, vector<unordered_set<int>>& graph) {
for (auto node : graph)
for (int n : node)
degrees[n]++;
}
//BFS要做的是维护一个维度表, 没有prerequisite的课的维度是0, 向后的课每层递增加1
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<unordered_set<int>> graph(numCourses);
makeGraph(graph, prerequisites);
vector<int> degrees(numCourses, 0);
//获取每个节点的度数
getDegrees(degrees, graph);
int count = 0;
queue<int> q;
//将所有和其他点有联通的点压入队列中
for (int i = 0; i < numCourses; i++)
if (!degrees[i])
q.push(i);
while (!q.empty()) {
int cur = q.front();
count++;
q.pop();
for (int n : graph[cur]) {
//if (!--degrees[n])，证明该点是一个键
if (!--degrees[n])
q.push(n);
}
}
return count == numCourses;
}Leetcode 310
题意：无向图，任意节点都可以视为根节点，将整个图转化为一棵树。输出所有使得该图的树高最小的根节点的值。
方法一：度为1的节点肯定不能是我们要的值，除非节点数小于3。选择非叶子结点，广度遍历。（头疼，这种解法现在还没改好）
方法二：可以先把每个叶子都视为根，找到最长的路径，最长路径中的中点就是我们要的根了（这样做会不会丢解？不清楚）。
方法三：每次都删除叶子节点，留下的就是使得树高最小的节点了。
#include"stdafx.h"
#include<iostream>
#include<vector>
#include<unordered_set>
using namespace std;
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
//记录每个节点的度数
vector<int> degrees(n, 0);
//哈希表
vector< unordered_set<int> > adjs(n, unordered_set<int>());
for (auto e : edges) {
auto nodeA = e.first;
auto nodeB = e.second;
degrees[nodeA]++;
degrees[nodeB]++;
adjs[nodeA].insert(nodeB);
adjs[nodeB].insert(nodeA);
}
//记录叶子节点
vector<int> candidateLeafs;
//临时容器，当某些节点的度减到1的时候，就把该节点删除。只记录度大于1的节点
unordered_set<int> candidateRoots;
for (size_t i = 0; i < n; i++) { candidateRoots.insert(i); }
do {
//更新叶子节点集合，因为每次循环删除所有度为1的节点（即叶子结点）
candidateLeafs.clear();
for (size_t i = 0; i < degrees.size(); i++) {
if (degrees[i] == 1) {
//记录当前叶子结点以及非叶子结点
candidateLeafs.push_back(i);
candidateRoots.erase(i);
}
}
for (auto i : candidateLeafs) {
//叶子结点的度数全部减1
degrees[i]--;
for (auto n : adjs[i]) {
//链接该叶子结点的节点的度减1
degrees[n]--;
//哈希表删除叶子结点
adjs[n].erase(i);
}
}
} while (candidateRoots.size() > 0 && candidateLeafs.size() > 0);
//条件成立，则证明candidateRoots.size()为0
if (candidateLeafs.size() > 0) { return candidateLeafs; }
vector<int> ret;
for (auto r : candidateRoots) { ret.push_back(r); }
return ret;
}
int main()
{
int n = 6;
vector<pair<int, int>> edges = { { 0, 1 },{ 0, 2 },{ 0, 3 },{ 3, 4 },{ 4, 5 } };
vector<int>answer = findMinHeightTrees(n, edges);
return 0;
}二叉查找树
LeetCode 230
思路：遍历之后将结果存入数组中，sort一下，读取第k个值？嗯。居然AC了，顺路复习了根据层序遍历结果来构造二叉树、三种遍历，并且探索了一下set
// 给定一个二叉搜索树，编写一个函数kthSmallest来查找其中第k个最小的元素
#include "stdafx.h"
#include<iostream>
#include<vector>
#include<queue>
#include<set>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
//函数声明
void Preorder(TreeNode *root, vector<int>&answer);
void Midorder(TreeNode *root, vector<int>&answer);
void Postorder(TreeNode *root, vector<int>&answer);
//复习利用按层遍历结果构造二叉树的过程
TreeNode* CreatTree(vector<int>&nums) {
size_t length = nums.size();
//如果nums的长度为零，说明树构不成了
if (length == 0) return nullptr;
int index = 0;
TreeNode* root = new TreeNode(nums[index]);
index++;
TreeNode* p = nullptr;
queue<TreeNode*>trans;
trans.push(root);
while (!trans.empty() && index < length) {
p = trans.front();
trans.pop();
if (index < length && nums[index] != -1) {
TreeNode *LeftNode = new TreeNode(nums[index]);
p->left = LeftNode;
trans.push(LeftNode);
}
index++;
if (index < length&&nums[index] != -1) {
TreeNode *RightNode = new TreeNode(nums[index]);
p->right = RightNode;
trans.push(RightNode);
}
index++;
}
return root;
}
//思路：遍历之后将结果存入数组中，sort一下，读取第k个值？嗯。
//闲来无事，复习各种遍历
int kthSmallest(TreeNode* root, int k) {
//存储前序遍历、中序遍历、后序遍历的结果
vector<int> answer_pre, answer_mid, answer_pos;
TreeNode* p = nullptr;
//前序遍历 根左右
Preorder(root, answer_pre);
//中序遍历
Midorder(root, answer_mid);
//后序遍历
Postorder(root, answer_pos);
set<vector<int> >temp;
temp.insert(answer_pre);
temp.insert(answer_mid);
temp.insert(answer_pos);
if (temp.size() == 1) {
//虽然三个vector中的元素相同，但是元素顺序不同，所以被视为三个了
//所以并没有输出"恭喜发财，红包拿来"
cout << "恭喜发财，红包拿来" << endl;
}
sort(answer_pre.begin(), answer_pre.end());
int answer=0;
answer = answer_pre[k - 1];
return answer;
}
//前序遍历 根左右
void Preorder(TreeNode *root,vector<int>&answer)
{
//根为空，则跳出函数
if (!root)
return ;
//存储根的值
answer.push_back(root->val);
//递归获取左子树的值
Preorder(root->left,answer);
//递归获取右子树的值
Preorder(root->right,answer);
}
//中序遍历 左根右
void Midorder(TreeNode *root, vector<int>&answer)
{
//根为空，则跳出函数
if (!root)
return;
//递归获取左子树的值
Midorder(root->left, answer);
//存储根的值
answer.push_back(root->val);
//递归获取右子树的值
Midorder(root->right, answer);
}
//后序遍历 左右根
void Postorder(TreeNode *root, vector<int>&answer)
{
//根为空，则跳出函数
if (!root)
return;
//递归获取左子树的值
Postorder(root->left, answer);
//递归获取右子树的值
Postorder(root->right, answer);
//存储根的值
answer.push_back(root->val);
}
int main()
{
int k = 0;
cin >> k;
vector<int>nums= { 3,5,1,6,2,0,8,-1,-1,7,4,-1,-1,-1,-1 };
//构造二叉树
TreeNode* root=CreatTree(nums);
//返回第k小的元素
int answer = kthSmallest(root, k);
return 0;
}
利用题意中树不是单纯的二叉树，而是一棵二叉搜索树，所以可以用递归，这样速度更快一点
（ 二叉搜索树的性质：https://blog.csdn.net/u013405574/article/details/51058133 ）
int find(TreeNode* root, int &k)
{
if (!root)
return 0;
int l = find(root->left, k);
//第k小的值在左子树中
if (k == 0)
return l;
k--;
//第k小的值是该节点
if (k == 0)
return root->val;
//第k小的值在右子树中
return find(root->right, k);
}
//递归法
int kthSmallest(TreeNode* root, int k) {
int answer = find(root, k);
int temp = answer;
return answer;
}LeetCode 449
题目挺长，感觉没什么意思，就是把一棵二叉搜索树里面的值转成一个字符串，然后再通过字符串恢复成树。
#include "stdafx.h"
#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<sstream>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* CreatTree(vector<int>&nums) {
size_t length = nums.size();
//如果nums的长度为零，说明树构不成了
if (length == 0) return nullptr;
int index = 0;
TreeNode* root = new TreeNode(nums[index]);
index++;
TreeNode* p = nullptr;
queue<TreeNode*>trans;
trans.push(root);
while (!trans.empty() && index < length) {
p = trans.front();
trans.pop();
if (index < length && nums[index] != -1) {
TreeNode *LeftNode = new TreeNode(nums[index]);
p->left = LeftNode;
trans.push(LeftNode);
}
index++;
if (index < length && nums[index] != -1) {
TreeNode *RightNode = new TreeNode(nums[index]);
p->right = RightNode;
trans.push(RightNode);
}
index++;
}
return root;
}
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (!root) return "#";
//分隔标志，后续有函数专门以空格为分隔符
string ans = " " + to_string(root->val);
return ans + serialize(root->left) + serialize(root->right);
}
TreeNode* DFS(istringstream &is)
{
string str;
//每次输出一个char类型的字符给str，字符串中各个字符以空格作为分界
is >> str;
if (str == "#") return NULL;
/*
string转int函数对比（返回值不同）
int stoi( const std::string& str, std::size_t* pos = 0, int base = 10 );
int stoi( const std::wstring& str, std::size_t* pos = 0, int base = 10 );
long stol( const std::string& str, std::size_t* pos = 0, int base = 10 );
long stol( const std::wstring& str, std::size_t* pos = 0, int base = 10 );
long long stoll( const std::string& str, std::size_t* pos = 0, int base = 10 );
long long stoll( const std::wstring& str, std::size_t* pos = 0, int base = 10 );
*/
TreeNode* root = new TreeNode(stoi(str));
//这一步妙
root->left = DFS(is),root->right = DFS(is);
return root;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
//istringstream对象可以绑定一行字符串，然后以空格为分隔符把该行分隔开来。
istringstream is(data);
size_t i = sizeof(data);
return DFS(is);
}
int main()
{
vector<int>nums={ 5,1,7,0,3,6,8,-1,-1,2,4,-1,-1,-1,-1 };
//构建二叉树
TreeNode* root=CreatTree(nums);
//编码 3 5 6## 2 7## 4## 1 0## 8##
string data=serialize(root);
//解码
TreeNode* answer=deserialize(data);
return 0;
}
LeetCode 315
从末尾往前扫描，当该数右侧的数比他小的时候，他在count中对应的值等于他右侧的数在count中所对应的值加1，当右侧的数比他大的时候向右扫描，找到比他小的数，他在count中对应的值就是找到的比他小的数在count中所对应的值加1.
经过算法实现，发现上述方法并不可行，比如输入[2,0,1]，它的输出为[1,0,0]。上述方法只不过是暴力搜索而已。
vector<int>answer;
vector<int>::iterator it = answer.begin();
//insert会改变容器的容量,这样可以实现倒着插
it=answer.insert(it,0);二叉查找树节点的后继是中序遍历时，遍历该节点时之后遍历的那个节点。后继节点是该节点的右子树中最小的那个点