算法笔记六数据结构——链表、栈、队列、哈希表、树、堆、图
layout: post
title: 算法笔记（六）数据结构——链表、栈、队列、哈希表、树、堆、图
description: 算法笔记（六）数据结构——链表、栈、队列、哈希表、树、堆、图
tag: 算法
数组
链表
栈与队列
栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。
栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。
栈的内部结构，栈的底层实现可以是vector，deque，list 都是可以的， 主要就是数组和链表的底层实现。
我们常用的SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的低层结构。
deque是一个双向队列，只要封住一段，只开通另一端就可以实现栈的逻辑了。
SGI STL中 队列底层实现缺省情况下一样使用deque实现的。
我们也可以指定vector为栈的底层实现，初始化语句如下：
std::stack<int, std::vector<int> > third; // 使用vector为底层容器的栈
栈的特性，对应的队列的情况是一样的。
队列中先进先出的数据结构，同样不允许有遍历行为，不提供迭代器, SGI STL中队列一样是以deque为缺省情况下的底部结构。
也可以指定list 为起底层实现，初始化queue的语句如下：
std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列
所以STL 队列也不被归类为容器，而被归类为container adapter（ 容器适配器）。
用栈实现队列
缓冲栈法
一个栈用于维持队列先进先出的顺序，另一个用作临时缓冲区
入队：push()
每次入队时，先将数据栈全压到缓冲栈中，再将入队元素压入缓冲栈顶，最后将缓冲栈全压回数据栈中。利用了缓冲栈，将新的元素压到数据栈的栈底，从而实现队列的后进后出
出队：pop()
由于数据栈出栈顺序维持着后进后出的规则，故出队直接弹出数据栈栈顶即可。
查看队头元素：peek()
数据栈的输出顺序与队列保持一致，故队头就是数据栈的栈顶top().
判断队列是否为空：empty()
数据栈存放了队列所有元素，所有检测数据栈是否为空即可。
输入输出栈法
方法二：
一个输入栈、一个输出栈
基本思路是每次入队时，将入队元素直接压入到输入栈，每次要出队时，判断输入栈是否为空，如果为空，将输入栈中的元素都压入到输出栈中，弹出输出栈栈顶元素，如果输出栈不为空，直接弹出输出栈顶。
入队：push()
将元素压入输入栈
出队：pop()
如果输出栈为空，将输入栈都压入输出栈，弹出输出栈栈顶。如果输出栈非空，直接弹出输出栈栈顶。
查看队头元素：peek()
由于每次出队的元素必是队头元素，因此可以利用pop()，获取到队头，由于peek()，只是查看一下队头元素，这里pop后，要再把该队头元素放回去，记录下获取的队头元素，将它再压入到输出栈的栈顶即可。
判断队列是否为空：empty()
两个栈都为空，才返回空。
相较而言，方法二明显元素移动次数要少，这里给出方法二的实现代码
class MyQueue {
public:
MyQueue() {
}
void push(int x) {
// 将x压入输入栈
stackIn.push(x);
}
int pop() {
// 输出栈为空时,将输入栈都压入到输出栈，弹出栈顶
if (stackOut.empty()) {
while (!stackIn.empty()) {
stackOut.push(stackIn.top());
stackIn.pop();
}
}
int res = stackOut.top();
stackOut.pop();
return res;
}
int peek() {
// 利用pop获取队头
int res = this->pop();
// 再将res压入输出栈栈顶
stackOut.push(res);
return res;
}
bool empty() {
return stackIn.empty() && stackOut.empty();
}
stack<int> stackIn;
stack<int> stackOut;
};
包含min函数的栈
由于栈是后进先出的原则，当前元素a直接压入栈的元素，在a弹出前必然留在栈中，故可以使用一个辅助栈，记录每次栈改变时当前数据栈中最小的值。即将当前时刻数据栈中的最小值记录在赋值栈的栈顶。
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
minStk.push(INT_MAX);
}
void push(int x) {
stk.push(x);
minStk.push(::min(x, minStk.top()));
}
void pop() {
stk.pop();
minStk.pop();
}
int top() {
return stk.top();
}
int min() {
return minStk.top();
}
stack<int> stk;
stack<int> minStk;
};
用队列实现栈
两个队列模拟
方法一：依旧是利用缓冲区调整顺序的思想。
入队：
后来的元素先放入缓冲队列，将数据队列出队再放入缓冲队列，此时在缓冲队列中，新来的元素在队头，与栈的数据顺序相同，故将缓冲队列与数据队列交换即可。
出队：直接从数据队列出队即可。
栈顶：就是数据队列队头
是否为空：判断数据队列是否为空即可。
一个队列模拟
方法二：将待入栈元素入队，将该元素前边所有元素出队再入队即可。
因为需要确定有多少元素需要出队后再入队，故需要记录下队列的长度。
这里同样给出更简单的实现，一个队列模拟：
class MyStack {
public:
MyStack() {
}
void push(int x) {
// 将队列中前边size个元素出队再入队
int count = que.size();
que.push(x);
while (count--)
{
que.push(que.front());
que.pop();
}
}
int pop() {
//
int ans = -1;
if (!que.empty()) {
ans = que.front();
que.pop();
}
return ans;
}
int top() {
return que.front();
}
bool empty() {
return que.empty();
}
queue<int> que;
};
栈的应用——逆波兰表达式求值
逆波兰表达式，也叫做后缀表达式。
我们平时见到的运算表达式是中缀表达式，即 “操作数① 运算符② 操作数③” 的顺序，运算符在两个操作数中间。
但是后缀表达式是 “操作数① 操作数③ 运算符②” 的顺序，运算符在两个操作数之后。
对逆波兰表达式求值的过程是：
1、如果遇到数字就进栈；
2、如果遇到操作符，就从栈顶弹出两个数字分别为 num2（栈顶）、num1（栈中的第二个元素）；计算 num1 运算 num2 .
一定要注意是先入栈的数操作后入栈的数！！！
int evalRPN(vector<string>& tokens) {
stack<long> stk;
for (string s : tokens) {
if (s == " " || s == "-" || s == "*" || s == "/")
{
long num1 = stk.top();
stk.pop();
long num2 = stk.top();
stk.pop();
// 这里一定要注意是num2操作num1，根据入栈顺序 实际上后弹出的num2是先入栈的，故放前边运算。
switch (s[0]) {
case ' ':
stk.push(num2 num1);
break;
case '-':
stk.push(num2 - num1);
break;
case '*':
stk.push(num2 * num1);
break;
case '/':
stk.push(num2 / num1);
break;
}
}
else
{
stk.push(stol(s));
}
}
int ans = stk.top();
stk.pop();
return ans;
}
单调栈
定义：单调栈：顾名思义，在栈中存储单调递增或递减顺序的结构。
特性：
自栈顶部到栈底部单调增加的单调栈用于生成某个数的极大区间，因为可以找到该数左右两边第一个比它大的值的位置，在这个区间内所有值都是小于该数的。
可以相信有一摞盘子，下边比上边大，当遇到一个比最上边还大的盘子时，就能确定这一摞盘子顶上的盘子，左边第一个比它大的是它下边的，右边比它大的是刚刚这个。
而如果改变单调栈的单调性，自栈顶部到栈底部是单调下降的话，则用于生成某个数的极小区间，因为可以利用单调栈找到该数左右两边第一个比它小的值。
单调栈用于解决：在一段数据中，为任意一个元素快速找左边和右边第一个比自己大/小的元素所在位置.
由于每个元素最多各自进出栈一次,复杂度是O(n).
无重复元素的单调栈
构栈流程：
维护栈从顶部到底部是升序的状态。
1、每次入栈判断当前元素是否比栈中元素小，是则将其索引入栈，否则开始将栈顶元素出栈，生成栈顶元素左右比自己大的元素所在位置信息。
2、再将待入栈元素与当前栈顶元素相比，若还是比待入栈元素小，将栈顶元素出栈，并生成信息。
3、假如遇到栈空的情况则表明，左边比没有比该元素还大的元素。将待入栈元素入栈。
4、若没有元素需要再入栈了，开始清算栈中剩余元素，每个要出栈的元素他右边比它还大的元素是无，他左边还他还大的元素是栈中当前元素底下一个的元素。
同样的当栈空时，说明当前元素左边没有比它还大的元素。
有重复元素的单调栈
基本流程一致，单调栈中存放链表，将相同元素压在一块，每次生成信息时，取链表尾部的元素索引。（尾部后入，离的最近）。
链表中出栈的顺序也是从尾部开始。
单调栈应用——下一次更高温天气
LeetCode739
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]
提示：
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100
题目显然是要求temperature数组中每个元素右边第一个比它大的元素所在的位置。非常适合采用单调栈的思路求解。
按照分类逻辑代码如下：
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
vector<int> ans(temperatures.size(), 0);
stack<int> stk;
for (int i = 0; i < temperatures.size(); i )
{
// 如果栈为空直接入栈，注意是根据元素大小比较，但栈中存放索引会更好，便于找到元素。
if (stk.empty())
{
stk.push(i);
}
else
{
while (!stk.empty())
{
// 这里要求右边第一个比它大(极大区间)，维持从栈顶到栈底升序
if (temperatures[stk.top()] < temperatures[i]) {
// 当前元素比栈顶元素大，说明当前元素即是栈顶元素右边第一个比它大的元素
ans[stk.top()] = i - stk.top();
stk.pop();
}
else
{
stk.push(i);
break;
}
}
if (stk.empty()) {
stk.push(i);
}
}
}
return ans;
}
};
精简后的代码如下：
核心是：循环判断：凡是栈不为空，且新来的元素比栈顶更大，生成栈顶的信息，弹出栈顶 循环结束时：一种可能是栈为空，那么入栈，一种可能是当前元素小于等于栈顶，也是入栈。
vector<int> dailyTemperatures(vector<int>& temperatures) {
vector<int> ans(temperatures.size(), 0);
stack<int> stk;
stk.push(0);
for (int i = 1; i < temperatures.size(); i )
{
// 如果栈为空直接入栈，注意是根据元素大小比较，但栈中存放索引会更好，便于找到元素。
while (!stk.empty() && temperatures[stk.top()] < temperatures[i])
{
// 当前元素比栈顶元素大，说明当前元素即是栈顶元素右边第一个比它大的元素
ans[stk.top()] = i - stk.top();
stk.pop();
}
stk.push(i);
}
return ans;
}
单调栈应用——接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
利用单调栈找到当前位置左右两边第一个比自身大的数字：
可以接到的雨水数量 = （区间宽度）* （两边界位置高度的较小值 - 当前位置高度）
int trap2(vector<int>& height) {
stack<int> stk;
stk.push(0);
int ans = 0;
for (int i = 1; i < height.size(); i )
{
while (!stk.empty() && height[stk.top()] < height[i])
{
// 令当前元素为栈顶
int cur = stk.top();
stk.pop();
// 栈顶元素下边是它的左边界
if (!stk.empty()) {
int left = stk.top();
ans = (i - left - 1) * (min(height[i], height[left]) - height[cur]);
}
}
stk.push(i);
}
return ans;
}
单调栈应用——柱状图最大矩形
LeetCode84
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
先给heights数组首尾加上0, 0（比较巧妙）
是以i 为中心，向左找第一个小于 heights[i] 的位置 left_i；向右找第一个小于于 heights[i] 的位置 right_i，即最大面积为 heights[i] * (right_i - left_i -1)，如下图所示：
/*
柱状图中最大的矩形
*/
int largestRectangleArea(vector<int>& heights) {
stack<int> st;
heights.insert(heights.begin(), 0); // 数组头部加入元素0
heights.push_back(0); // 数组尾部加入元素0
st.push(0);
int result = 0;
for (int i = 1; i < heights.size(); i ) {
while (heights[i] < heights[st.top()]) {
int mid = st.top();
st.pop();
// 由于在heights数组头部插入了0，故栈中必定会留有一个0,不被弹出，所以不需要判断栈非空
int w = i - st.top() - 1;
int h = heights[mid];
result = max(result, w * h);
}
st.push(i);
}
return result;
}
单调队列
单调队列：顾名思义是在队列中存储单调递增或递减的数据段，用于可以随时输出一段数据的最值。
一个滑动窗口由左右边界（L和R决定，其中L<=R），维护一个双端队列，存放数字的索引，每次R右移时，会向窗口中添加一个元素，如果该元素比队尾数字小，直接放入队尾，否则循环将队尾元素弹出，直至队尾元素大于当前元素或者队列为空。
（因为前边放入的元素先过期，而当存在比先过期的元素更大的元素后，这些先过期的元素永远不可能再成为最大的元素，所以不需要再维护这些元素），
L右移时，查看L左侧的元素是否为队列中的队头元素，如果是，将队列中的队头从队头弹出，如果不是，跳过。
单调队列数据结构：pop()从数据段左边删掉一个元素push()向数据段中加入一个元素front()获取队头，即当前滑动窗口的最大值
class MonoQueue
{
public:
void pop(int value) {
// 假如弹出的元素是队头
if (!dque.empty() && dque.front() == value) {
dque.pop_front();
}
}
void push(int value) {
while (!dque.empty() && dque.back() < value) {
dque.pop_back();
}
dque.push_back(value);
}
int front() {
return dque.front();
}
private:
deque<int> dque;
};
单调队列应用——求滑动窗口最大值
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
用上边实现的单调栈结构可以很好的解决：
先将第一个窗口的数据放入单调栈中注意这里窗口的边界采用了左闭右开区间
故窗口移动时;
monoQue.push(nums[right ]);
monoQue.pop(nums[left ]);
ans.push_back(monoQue.front());
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MonoQueue monoQue;
int left = 0, right = k;
vector<int> ans;
// 先将k个数放入单调栈中
for (int i = 0; i < k; i )
{
monoQue.push(nums[i]);
}
ans.push_back(monoQue.front());
// 循环右移窗口
while (right < nums.size())
{
monoQue.push(nums[right ]);
monoQue.pop(nums[left ]);
ans.push_back(monoQue.front());
}
return ans;
}
优先级队列（priority_queue）
C STL中内置了优先级队列这个数据结构，优先队列的本质是堆，但它具有队列的所有操作特性，与普通队列不同的地方就是出队的时候按照优先级顺序出队，这个优先级即最大堆或最小堆的规则（即大的为top优先出队或小的为top优先出队），在队列的基础上加了个堆排序。
基本操作
它的基本操作和队列基本操作相同：
- top 访问队头元素
- empty 队列是否为空
- size 返回队列内元素个数
- push 插入元素到队尾 (并排序)
- emplace 原地构造一个元素并插入队列
- pop 弹出队头元素
- swap 交换内容
使用示例：
优先级队列默认情况下是大根堆，当然也可以在声明时，指定排序规则：
//升序队列，小顶堆
priority_queue <int,vector<int>,greater<int> > q;
//降序队列，大顶堆
priority_queue <int,vector<int>,less<int> >q;
//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）
通常我们使用优先级队列时，会存放我们自定义的数据类型，因此，一般我们需要自己定义比较器。
以题目为例
LeetCode347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
首先，我们可以使用哈希表（值为key，频次为value）统计nums数组中每个元素出现的次数。
随后我们维护一个大小为K的小根堆，每个节点就是哈希表中的键值对，比较规则就是键值对的value，因为要返回频率前k高的元素。选择小根堆是因为，小根堆的优先级队列是频次小的优先出队，因此最后留在堆中的就是前K高的节点。
由于是自定义的数据类型，因此需要自定义比较器：
比较器实际上就是比较时所执行的谓词函数。
class myComparion
{
public:
bool operator()(const pair<int, int> &node1, const pair<int, int> &node2) {
return node1.second > node2.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
// 统计元素出现频率
unordered_map<int, int> umap;
for (int num : nums) {
umap[num] ;
}
// 构建小根堆对频次排序
priority_queue<pair<int, int>, vector<pair<int, int>>, myComparion> pri_que;
// 用固定大小为K的小根堆存放map中每个元素
for (unordered_map<int, int>::iterator it = umap.begin(); it != umap.end(); it ) {
pri_que.push(*it);
// 如果节点数大于k，弹出
if (pri_que.size() > k) {
pri_que.pop();
}
}
// 此时小根堆中就是前K高频的节点，然而它是频次低的先出堆，因此将节点转到结果数组中，从数据尾部插入
vector<int> ans(k);
for (int i = k - 1; i >= 0; i--)
{
ans[i] = pri_que.top().first;
pri_que.pop();
}
return ans;
}
二叉树
定义与概念
- 二叉树节点的定义：
struct TreeNode
{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}; // 节点的构建函数
};
-
重要概念
二叉树的深度：就是二叉树的层数叶子节点：二叉树的底层，左右子节点都为空的末尾节点。二叉树的度：二叉树中结点与结点的连线就叫做度。满二叉树：除叶子节点外每个节点都有两个子节点，即二叉树的每一层都是满的完全二叉树：如果按照从上到下，从左到右给二叉树的每个节点编号（包括为空的节点），如果一棵树最终得到的编码结果与满二叉树是一致的，称它为完全二叉树。 -
基本性质
- 二叉树中第m层最多有2(m-1) 个节点，根节点是第一层。
- 节点数 = 总度数 1。
- 高度为k的二叉树，最多有2 k - 1个节点。
- 对于一颗完全二叉树，根节点从0开始编号，编号为
k的节点，它的父节点编号为(k - 1) / 2，它的左孩子节点编号为2*k 1，右孩子节点编号为2*k 2 - 二叉树的存储方式既可以通过节点
链式存储，也可以利用完全二叉树编号的方式存在数组或队列中。上边将到的堆，实际上就是一种完全二叉树，因为他是将数据存放在队列中，故又称为优先级队列
二叉树类型
满二叉树与完全二叉树
除最后一层无任何子节点（都是叶子节点）外，每一层上的所有节点都有两个子节点，称为满二叉树
一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
二叉搜索树与平衡二叉树
二叉搜索树是一种有序数，满足左节点 < 父节点 < 右节点
所有的子树左子树和右子树之间的高度差≤1是平衡二叉树
二叉树的遍历方式
递归遍历
前序：头左右
中序：左头右
后序：左右头
不论前中后序，左右节点的相对遍历顺序不变，都是先左后右，因此递归时，必是先递归调用左节点，再递归调用右节点。
不同顺序的区别在于头节点遍历，或者说是打印的时机：
假设最终要将二叉树节点每个值存放到一个数组nums中：
递归版本如下：
void traverse(TreeNode* node, vector<int> &nums) {
if (node == nullptr) {
return;
}
// nums.push_back(node->val); // 打印时机1 先序
traverse(node->left, nums);
// nums.push_back(node->val); // 打印时机2 中序
traverse(node->right, nums);
// nums.push_back(node->val); // 打印时机3 后序
}
vector<int> preOrderRecur(TreeNode* root) {
vector<int> ans;
traverse(root, ans);
return ans;
}
递归函数中三个打印时机时机上就对应了前、中、后序三种遍历方式。
每个节点都会回到递归函数中三次：
在何时打印，决定了最后的顺序。
从下边的例子可以看出，
- 每次取第一次进入递归函数时的数据，则最终得到先序
- 每次取第二次进入递归函数时的数据，则最终得到中序
- 每次取第三次进入递归函数时的数据，则最终得到后序
迭代遍历
前序：
使用一个辅助栈存放节点，每次从栈中弹出元素时打印，由于前序是头左右，故入栈时先将右节点入栈，后左节点入栈。
/*
前序：核心在于出栈时打印，子节点入栈时先右再左，从而保证时出栈时为头左右的前序
*/
vector<int> preOrder(TreeNode* root) {
vector<int> ans;
if (root == nullptr) {
return ans;
}
stack<TreeNode*> stk;
stk.push(root);
while (!stk.empty())
{
TreeNode* cur = stk.top();
stk.pop();
ans.push_back(cur->val);
if (cur->right != nullptr) {
stk.push(cur->right);
}
if (cur->left != nullptr) {
stk.push(cur->left);
}
}
return ans;
}
后序：
后序是左右头，在先序中，对于子节点，我们先右再左入栈，在出栈时打印，实现了头左右的顺序，假设修改入栈时为先左后右，则可以得到头右左的顺序，这个顺序逆序后，恰好就是左右头的后序。
/*
先序时，先右后左入栈，实现了出栈打印时为，头左右，假设入栈先左后右，则实现了头右左，再逆序就是左右头的后序
*/
vector<int> postOrder(TreeNode* root) {
vector<int> ans;
if (root == nullptr) {
return ans;
}
stack<TreeNode*> stk;
stk.push(root);
while (!stk.empty())
{
TreeNode* cur = stk.top();
stk.pop();
ans.push_back(cur->val);
// 先左
if (cur->left != nullptr) {
stk.push(cur->left);
}
// 后右
if (cur->right != nullptr) {
stk.push(cur->right);
}
}
// 再逆序
reverse(ans.begin(), ans.end());
return ans;
}
中序：
在前序遍历时，因为每次我们是先访问到头节点，而前序要求的也是先打印头节点，故处理起来比较容易。中序遍历时，左头右，的顺序，我们访问到头节点时，还不能直接打印头结点的数据。
那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问最底层节点，栈则用来处理打印节点上的元素。
操作时：
- 初始时当前节点cur为根节点
- 如果cur不为空，把cur放入栈中，cur = cur ->left
- 如果cur为空，说明左节点已经全部入栈，cur = 弹出的栈顶元素，打印，cur = cur ->right。
- 当栈非空或者cur非空，一直重复1-3
有必要结合中序遍历的路径理解代码：中序：cur指针用来找到最左节点，stk记录节点，没有最左节点时，cur置于栈顶节点，打印cur后，弹出，cur = cur->right
/*
中序：cur指针用来找到最左节点，stk记录节点，没有最左节点时，cur置于栈顶节点，打印cur后，弹出，cur = cur->right
*/
vector<int> inOrder(TreeNode* root) {
vector<int> ans;
if (root == nullptr) return ans;
stack<TreeNode*> stk;
TreeNode* cur = root;
while (cur != nullptr || !stk.empty())
{
if (cur != nullptr) {
stk.push(cur);
cur = cur->left;
}
else{
cur = stk.top();
stk.pop();
ans.push_back(cur->val);
cur = cur->right;
}
}
return ans;
}
层序遍历
层序遍历的本质是广度优先搜索。
借助一个队列，将每一层的节点打印的同时，将当前层节点的子节点添加到队列中。这样本层打印结束时，下一层元素也都进入了队列中。
关键在于如果判断当前层结束了呢？
一开始时，将根节点放入队列，根节点打印完毕时，根节点被弹出，第二层节点全部入队列，第二层节点全部打印完毕时，第三层节点全部入队列。因此，刚开始队列的长度就是本层的节点数，记录下队列的长度，用for循环遍历即可。
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
queue<TreeNode*> que;
if (root != nullptr) que.push(root);
while (!que.empty())
{
int size = que.size();
vector<int> path;
for (int i = 0; i < size; i )
{
path.push_back(que.front()->val);
if (que.front()->left != nullptr) que.push(que.front()->left);
if (que.front()->right != nullptr) que.push(que.front()->right);
que.pop();
}
ans.emplace_back(path);
}
return ans;
}
Morris遍历
Morris遍历利用了二叉树中叶子节点的空闲空指针，加速二叉树的遍历过程。 通常的变量方式，每个节点遍历时会访问3次，而Morris遍历，如果一个节点具有左子树，则会访问2次，如果没有左子树则只访问1次。
Morris遍历定义的标准：
- 定义一个遍历指针cur，该指针首先指向头结点
- 判断cur的左子树是否存在
- 如果cur的左孩子为空，说明cur的左子树不存在，那么cur右移来到cur.right
- 如果cur的左孩子不为空，说明cur的左子树存在，找出该左子树的最右结点，记为mostRight
- 如果，mostRight的右孩子为空，那就让其指向cur（mostRight.right=cur），并左移cur（cur=cur.left）
- 如果mostRight的右孩子不空，那么让cur右移（cur=cur.right），并将mostRight的右孩子置空
- 经过步骤2之后，如果cur不为空，那么继续对cur进行步骤2，直至cur = nullptr
下图所示举例演示morris遍历的整个过程：
注意：
左子树的mostRight求解方法就是一直询问节点是否有右孩子，有则右移，没有则说明到了最右。- 对于每个有左子树的节点，我们都会找到它的左子树最右节点mostRight，将它的右指针指向cur，便于后边遍历时能回来，因此
Morris遍历对于每个有左子树的节点会访问2次，其余节点只访问一次。
对于上边1-7的完全二叉树，Morris遍历的结果为：Morris序：1 2 4 2 5 1 3 6 3 7先序：1 2 4 5 3 6 7中序：4 2 5 1 6 3 7后序：4 5 2 6 7 3 1
vector<int> morris(TreeNode* root) {
vector<int> ans;
TreeNode* cur = root;
while (cur != nullptr)
{
ans.push_back(cur->val);
// 先判断是否有左子树
if (cur->left != nullptr) {
// 如果有左子树，找到左子树最右的节点
TreeNode* mostRight = cur->left;
// 终止条件为左子树最右节点的右指针指向了自己或者指向空
while (mostRight->right != nullptr && mostRight->right != cur)
{
mostRight = mostRight->right;
}
// 如果左子树最右节点的右指针指向为空，将它改为指向cur，便于后边的遍历
if (mostRight->right == nullptr) {
mostRight->right = cur;
// cur 左移
cur = cur->left;
}else{
// 先利用mostRight指针右移cur，注意这里cur其实就是mostRight
cur = cur->right;
// 修改回去
mostRight->right = nullptr;
}
}
else{
// 如果没有左子树，直接右移cur
cur = cur->right;
}
}
return ans;
}
Morris遍历改前序、中序
Morris序对比前序和中序可知，对于重复访问的节点，每次只保留第一次访问的结果就是前序遍历，而每次保留第二次访问的结果就是中序。
那么由Morris序改前序和中序问题的关键就在于如何判断是第一次访问某个节点还是第二次访问。
首先对于左子树为空的节点，一定只访问一次，因此如果左子树为空的节点直接打印。
对于左子树不为空的节点，求mostRight，mostRight右指针为空说明是第一次访问，mostRight右指针不为空说明是第二次访问。
Morris序：1 2 4 2 5 1 3 6 3 7先序：1 2 4 5 3 6 7中序：4 2 5 1 6 3 7
Morris改前序，重点在于，左子树为空直接打印，左子树不为空，求mostRight，mostRight右指针为空，是第一次访问打印。
/*
Morris改前序
*/
vector<int> morrisPre(TreeNode* root) {
vector<int> ans;
TreeNode* cur = root;
while (cur != nullptr)
{
// 先判断是否有左子树
if (cur->left != nullptr) {
// 如果有左子树，找到左子树最右的节点
TreeNode* mostRight = cur->left;
// 终止条件为左子树最右节点的右指针指向了自己或者指向空
while (mostRight->right != nullptr && mostRight->right != cur)
{
mostRight = mostRight->right;
}
// 如果左子树最右节点的右指针指向为空，将它改为指向cur，便于后边的遍历
if (mostRight->right == nullptr) {
mostRight->right = cur;
// cur 左移
// mostRight右指针为空是第一次访问cur，先序取第一次
ans.push_back(cur->val);
cur = cur->left;
}
else {
// 先利用mostRight指针右移cur，注意这里cur其实就是mostRight
cur = cur->right;
// 修改回去
mostRight->right = nullptr;
}
}
else {
// 如果没有左子树，直接右移cur
// 没有左子树的节点访问一次，直接打印
ans.push_back(cur->val);
cur = cur->right;
}
}
return ans;
}
Morris改中序，重点在于，左子树为空直接打印，左子树不为空，求mostRight，mostRight右指针为cur，是第二次访问，打印。
/*
Morris改中序
*/
vector<int> morrisIn(TreeNode* root) {
vector<int> ans;
TreeNode* cur = root;
while (cur != nullptr)
{
// 先判断是否有左子树
if (cur->left != nullptr) {
// 如果有左子树，找到左子树最右的节点
TreeNode* mostRight = cur->left;
// 终止条件为左子树最右节点的右指针指向了自己或者指向空
while (mostRight->right != nullptr && mostRight->right != cur)
{
mostRight = mostRight->right;
}
// 如果左子树最右节点的右指针指向为空，将它改为指向cur，便于后边的遍历
if (mostRight->right == nullptr) {
mostRight->right = cur;
// cur 左移
cur = cur->left;
}
else {
// 先利用mostRight指针右移cur，注意这里cur其实就是mostRight
// mostRight右指针非空，是第二次访问，中序取第二次访问
ans.push_back(cur->val);
cur = cur->right;
// 修改回去
mostRight->right = nullptr;
}
}
else {
// 如果没有左子树，直接右移cur
// 没有左子树的节点访问一次，直接打印
ans.push_back(cur->val);
cur = cur->right;
}
}
return ans;
}
Morris遍历改后序
Morris序：1 2 4 2 5 1 3 6 3 7后序：4 5 2 6 7 3 1
使用Morris改后序较为复杂。
参见这里
二叉树递归解题思路
利用递归可以很轻易地将二叉树问题化解为，求左子树的状态，右子树状态，从而求整个树的状态。
模板写法：
- 构建一个类，包含需要向子树索取的信息
- 编写递归函数，递归向子树索取信息，父节点根据左右子树索取到的信息，构建自身的信息返回。
- 主函数调用递归函数传入根节点。
下边这个求二叉树直径的例子，几乎可以作为解二叉树DP问题的
题目：
LeetCode543.求二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
基本思路：题目已经提示，这条最长的路径，可能穿过根节点，也可能不会穿过根节点。
情况一：经过根节点，那么最大路径就是左子树高度加右子树高度
情况二：不经过根节点，那么最大路径就是左子树的直径和右子树直径的最大值。
因此假如有一个递归函数，可以获取的子树的高度和最大直径，就可以知道父节点的最大直径。
基于此思路，先构建一个信息类，包含两个变量树高和树的直径。
递归函数，返回一个节点的树的信息。
base case 节点为空时，自然高度和直径都为0；
递归函数的关键在于，节点不为空时，基于左右子树的信息，构建自身树的信息的处理。
/*
求二叉树的直径
*/
class TreeDiameter
{
public:
class Info
{
public:
Info(int _height, int _distance) {
height = _height;
distance = _distance;
}
int height;
int distance;
};
Info getInfo(TreeNode* root) {
if (root == nullptr) return Info(0, 0);
Info left = getInfo(root->left);
Info right = getInfo(root->right);
int height = max(left.height, right.height) 1;
int distance = max(left.height right.height, max(left.distance, right.distance));
return Info(height, distance);
}
int diameterOfBinaryTree(TreeNode* root) {
return getInfo(root).distance;
}
};
翻转二叉树
LeetCode226、翻转二叉树
递归函数用于翻转二叉树，而实际上可以通过翻转根节点的左子树和右子树再交换左右子树即可。
base case为节点为空，空节点不做处理，非空节点，翻转左子树和右子树，交换左右子树。
TreeNode* invertTree2(TreeNode* root) {
if (root == nullptr) {
return root;
}
TreeNode* leftNode = invertTree2(root->left);
TreeNode* rightNode = invertTree2(root->right);
root->left = rightNode;
root->right = leftNode;
return root;
}
相同的树
判断两棵树是否相等，等价判断两棵树的左子树是否相同，右子树是否相同，头结点的值是否相同。
base case 还是两个节点有为空的情况：
假如两节点为空的情况不一致，则也不同
两节点不为空，先判断两节点对应的值是否相同，如果相同再判断左右子树是否对应相同。
bool isSameTree(TreeNode* p, TreeNode* q) {
if (p == nullptr && q == nullptr) {
return true;
}
else if (p == nullptr || q == nullptr) {
return false;
}
else if (p->val != q->val) {
return false;
}
else {
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
}
对称二叉树
LeetCode101、给定一个二叉树，检查它是否是镜像对称的。
对称二叉树，实际上是比较左右子树是否镜像相等。
递归函数用于比较两棵树是否镜像相等。
所谓镜像相等，首先两棵树根节点相等，其次树1的左子树镜像相等树2的右子树，树1的右子树镜像相等树2的左子树。
base case还是两节点为空的情况，当不为空时，先判断两节点的值是否相等，如果相等，比较左子树的左子树和右子树的右子树（外侧）是否镜像相等，比较比较左子树的右子树和右子树的左子树（外侧）是否镜像相等，同时镜像相等，表明整体镜像相等。
/*
对称二叉树
*/
bool compareTree(TreeNode* left, TreeNode* right) {
if (left == nullptr && right != nullptr) return false;
else if (left != nullptr && right == nullptr) return false;
else if (left == nullptr && right == nullptr) return true;
else if (left->val != right->val) return false;
else
{
bool outside = compareTree(left->left, right->right);
bool inside = compareTree(left->right, right->left);
return outside && inside;
}
}
bool isSymmetric(TreeNode* root) {
if (root == nullptr) return true;
return compareTree(root->left, root->right);
}
完全二叉树节点的个数
对于满二叉树，它的节点个数可以由树深直接求出，而完全二叉树可以分解为若干满二叉树。
因此可以采用递归的方法，直至递归到满二叉树，直接根据数深计算节点个数。
满二叉树的特性：左孩子一直遍历左孩子的左孩子，得到树的左斜边，右孩子一直遍历右孩子的右孩子，得到树的右斜边，遍历过程中统计深度，如果左右深度一致，则是完全二叉树，直接根据深度计算节点数，否则节点数为递归求左孩子节点数 递归求右孩子节点数 1（自身）
int countNodes(TreeNode* root) {
if (root == nullptr) return 0;
TreeNode* left = root->left;
TreeNode* right = root->right;
int leftDeep = 0;
int rightDeep = 0;
while (left != nullptr)
{
left = left->left;
leftDeep ;
}
while (right != nullptr)
{
right = right->right;
rightDeep ;
}
if (leftDeep == rightDeep) return (2 << leftDeep) - 1;
return countNodes(root->left) countNodes(root->right) 1;
}
二叉树两节点的最低公共祖先
LeetCode235
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。
基本思路：
-
求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历的方式。
-
递归函数向左右子树找p或者q，base case 为节点为空或者为p，q，返回节点。
-
如果左子树找到了p或q，右子树也找到了p或者q，即递归结果非空，则说明最低公共祖先就是root，否则如果左子树返回结果为空，如果p和q都在右子树上边被发现，将右子树找到的结果返回。
不断向左右子树要p或者q，如果同时找到p和q，返回root，否则将p和q不断向上返回。
TreeNode* lowestCommonAncestor2(TreeNode* root, TreeNode* p, TreeNode* q) {
if (p == root || q == root || root == nullptr) return root;
TreeNode* left = lowestCommonAncestor2(root->left, p, q);
TreeNode* right = lowestCommonAncestor2(root->right, p, q);
if (left != nullptr && right != nullptr) return root;
if (left != nullptr) return left;
return right;
}
二叉树的回溯解法
二叉树的题目首选递归法，其次选回溯法
回溯解法本质上是对所有可能的暴力尝试，二叉树本身在遍历时也面临着考虑走左还是走右的问题，很符合应用回溯的思路解题。
举个最通俗的求路径种类的例子
LeetCode257、给定二叉树求所有路径
节点数目在[1, 100]
解法回溯：
参数：当前节点，路径pah，所有路径组合ans
终止条件：当前节点为叶子节点
对于每个节点，如果是叶子节点，插入节点值，终止。
如果非叶子节点，如果左节点非空，path插入当前节点值，插入“->”，递归左节点。如果右节点非空，path插入当前节点值，插入“->”。
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> ans;
string path;
treePathBacktracking(root, path, ans);
return ans;
}
void treePathBacktracking(TreeNode* cur, string path, vector<string> &ans) {
if (cur == nullptr) return;
if (cur->left == nullptr && cur->right == nullptr) {
path = to_string(cur->val);
ans.emplace_back(path);
return;
}
path = to_string(cur->val);
path = "->";
if (cur->left != nullptr) {
treePathBacktracking(cur->left, path, ans);
}
if (cur->right != nullptr) {
treePathBacktracking(cur->right, path, ans);
}
}
二叉搜索树题目
二叉搜索树的查、增 、删
- 查询节点key
递归：
base case 为当前节点为空或者节点值为key，返回该节点。
若key大于节点值，搜索右子树，否则搜索左子树。
if (root == nullptr || root->val == val) return root;
if (root->val > val) return searchBST(root->left, val);
return searchBST(root->right, val);
- 增加
搜索二叉树的增加就是搜索二叉树的构建过程，规则一般是第一个元素作为根节点，若第二个元素的小于第二个则添加到左边，若大于则添加到右边。
二插搜索树一般不能有重复的元素，但可以通过修改节点的结构，每个节点不仅放元素的值value，同时统计元素出现的次数count。
可以通过递归的思路实现二叉搜索树的增加，
base case 是节点为空，则直接创建一个值为val的节点返回。
节点非空，若节点值大于val，说明val需要构建在该节点的左子树，否则说明需构建在该节点的右子树上。
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(root == nullptr){
root = new TreeNode(val);
}
if (val > root->val) root->right = insertIntoBST(root->right, val);
if (val < root->val) root->left = insertIntoBST(root->left, val);
return root;
}
- 删除
删除某个节点分为三种情况
- 该节点没有子节点
这种情况下，每次遍历节点时同时记录父节点（根节点父节点是本身），定位到该节点时将父节点指向该节点，修改为指向空，释放删除的节点。 - 该节点只有一个子节点
与情况1类似，将父节点指向该节点，修改为指向该节点的子节点，释放删除的节点。 - 该节点有两个子节点
这种情况需要注意，待删除节点的父节点只有一个指向该节点的指针，但是该节点却有两棵子树，如何确定连接方式呢？（1）将该节点左子树的最右节点（6号），记录保存下来，因为它是最右边的节点，因此它一定满足上边的情况1和情况2，按照上边的做法，删除这个最右边节点，将待删除节点7号的父节点指向保存下来的6号节点，将6号节点的左指针指向7号的左子树，右指针指向7号的右子树，删除并释放7号节点。
简单讲就是：保存左子树最右节点，删除该节点，用保存下的左子树最右节点替换 待删除节点。
根据搜索二叉树的定义，左子树最右节点是左子树的最大值（潜台词，左子树除最右节点外所有节点都小于该最右节点），右子树上每个值都会大于左子树（潜台词，右子树上每个节点都大于左子树最右节点），因此这样替换后，可以保证6号节点左边都是小于6号节点的值，右边都是大于6号节点的节点，删除节点同时，保证了搜索二叉树的合法性。
同理，将右子树的最左节点保存记录后再删除，替换待删除节点也是可行方案，因为右子树除最左节点外都大于该最左节点，左子树都小于该右子树的最左节点。
代码实现上，注意是情况三，待删除节点节点有两个孩子节点的情况，可以找到该节点的左子树最右，将待删除节点的值修改为左子树最右的值，然后该节点的左子树等于删除左子树最右节点后的树。将删除节点替换后，把问题转换为了删除左子树最右节点的子问题
/*
删除二叉搜索树某个节点
*/
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return root;
if (root->val > key) {
root->left = deleteNode(root->left, key);
}
else if(root->val < key){
root->right = deleteNode(root->right, key);
}
else
{
// 节点值即为key
// 任意子节点为空的情况，将另一个子树返回，即删除了该树的根节点
if (root->left == nullptr) return root->right;
if (root->right == nullptr) return root->left;
// 到这里，说明是左右子树都有，找左子树最右或者右子树最左替换该节点
TreeNode* mostRight = root->left;
while (mostRight->right != nullptr)
{
// 这里选择的是找左子树最右
mostRight = mostRight->right;
}
// 修改该节点值为左子树最右的值
root->val = mostRight->val;
// 将左子树替换为删除左子树最右后的左子树
root->left = deleteNode(root->left, mostRight->val);
}
return root;
}
修剪二叉搜索树到区间[low, high]
如果节点为空，直接返回。
如果节点值小于低阈值，该节点左子树一定是不需要的，返回在右子树找的结果。
如果节点值大于高阈值，该节点右子树一定是不需要，返回在左子树上找的结果。
否则，在左右子树上分别找在区间的树。
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root == nullptr) return root;
if (root->val < low) return trimBST(root->right, low, high); // root left < low
if (root->val > high) return trimBST(root->left, low, high); // root right > high
// low <= val <= high
root->left = trimBST(root->left, low, high);
root->right = trimBST(root->right, low, high);
return root;
}
有序数组构建搜索二叉树
每次取有序数组中间值建立根节点，在中间值左区间，构建节点，接上根节点左孩子，右区间构建节点接上根节点右孩子。
TreeNode* sortedArrayToBST(vector<int>& nums) {
return arrayToTree(nums, 0, nums.size() - 1);
}
TreeNode* arrayToTree(vector<int> &nums, int left, int right) {
if (left > right) return nullptr;
int mid = left (right - left) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = arrayToTree(nums, left, mid - 1);
root->right = arrayToTree(nums, mid 1, right);
return root;
}
将搜索二叉树转为累加树
给定一个二叉搜索树 root (BST)，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。
观察可知，这里的累计树是反中序累加，即根据右中左的顺序，把前一个节点的值加到该节点即可。
逆中序实现的方式有很多，只需要在中序的基础上，把left和right对调即可。
/*
从二叉搜索树构建累计二叉树
*/
// 反中序遍历， 右中左
void accumSumTree(TreeNode* root, int &pre) {
if (root == nullptr) return;
accumSumTree(root->right, pre);
root->val = pre;
pre = root->val;
accumSumTree(root->left, pre);
}
TreeNode* bstToGst(TreeNode* root) {
int pre = 0;
accumSumTree(root, pre);
return root;
}
二叉树的序列化与反序列化
或通过符合标记，或是通过遍历顺序，如果能够唯一确定一颗二叉树，那么称为完成了二叉树的序列化，因为序列化是唯一确定一颗树的，那么一定可以通过序列化反向生成这棵树。下面是常见的序列化和反序列的题目。
从中序和后序构造二叉树
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
主要思路，中序是左头右，后序是左右头，因此后序的最后一个元素一定是中间节点，由这个中间节点，找到中序中对应元素，即可在中序里边，把中序序列分为左子树序列和右子树序列，根据中序序列的左子树序列和右子树序列来分割后序序列为左右两部分，中序依据头节点分割，后序的的左右连在一块，依据中序中左子树序列的长度，即可将后序的左右连续区间分割为两部分。
根据左后序和左中序构建左子树节点，
根据右后序和右中序构建右子树节点。
递归base case：
节点为空，返回null
后序序列长度为1，后序最后一个就是整个树。
root->left = buildTree(leftInorder, leftPostorder);
root->right = buildTree(rightInorder, rightPostorder);
return root;
/*
从中序和后序遍历构建二叉树
*/
TreeNode* buildTree(vector<int>& inorderArr, vector<int>& postorderArr) {
if (postorderArr.size() == 0) return nullptr;
TreeNode* root = new TreeNode(postorderArr[postorderArr.size() - 1]);
if (postorderArr.size() == 1) return root;
int index = 0;
for (int i = 0; i < inorderArr.size(); i )
{
if (inorderArr[i] == root->val) {
index = i;
break;
}
}
// 依据头结点的index分割中序为左中序和右中序
vector<int> leftInorder(inorderArr.begin(), inorderArr.begin() index);
vector<int> rightInorder(inorderArr.begin() index 1, inorderArr.end());
// 依据左中序的长度，分割后序为，左后序和右后序
vector<int> leftPostorder(postorderArr.begin(), postorderArr.begin() leftInorder.size());
vector<int> rightPostorder(postorderArr.begin() leftInorder.size(), postorderArr.end() - 1);
root->left = buildTree(leftInorder, leftPostorder);
root->right = buildTree(rightInorder, rightPostorder);
return root;
}
这篇好文章是转载于：学新通技术网
- 版权申明： 本站部分内容来自互联网，仅供学习及演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，请提供相关证据及您的身份证明，我们将在收到邮件后48小时内删除。
- 本站站名： 学新通技术网
- 本文地址： /boutique/detail/tanhegaafg
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储，并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01
