c++之二叉树
1、二叉树的递归
递归三要素
-
确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
-
确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
-
确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
class Solution {
public:
void traversal(TreeNode* cur, vector<int>& vec) //确定递归函数的参数和返回值
{
if (cur == NULL) return; // 终止条件
vec.push_back(cur->val); // 中 单层递归逻辑
traversal(cur->left, vec); // 左 单层递归逻辑
traversal(cur->right, vec); // 右 单层递归逻辑
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};深度前序遍历的过程
2、 二叉树的遍历方式
1、深度优先
先往深走，遇到叶子节点再往回走
前序遍历（递归法，迭代法）
中序遍历（递归法、迭代法）
后序遍历（递归法、迭代法）
递归法
前序遍历 （根、左、右）
class Solution{
public:
void traversal(TreeNode* cur vector<int>& vec)
{
if(cur == NULL) return; //终止条件
//单层逻辑
vec.push_back(cur ->val);//根
traversal(cur ->left,vec);//左
traversal(cur ->right,vec);//右
}
vector<int> preorderTraversal(TreeNode* root)
{
vector<int> result;
traversal(root,result);//将树传入生成数组
return result;
}
}中序遍历 （左、根、右）
class Solution{
public:
void traversal(TreeNode* cur vector<int>& vec)
{
if(cur == NULL) return; //终止条件
//单层逻辑
traversal(cur->left,vec);//左
vec.push_back(cur ->val);//根
traversal(cur->right,vec);//右
}
vector<int> preorderTraversal(TreeNode* root)
{
vector<int> result;
traversal(root,result);//将树传入生成数组
return result;
}
}后序遍历（左、右、根）
class Solution{
public:
void traversal(TreeNode* cur vector<int>& vec)
{
if(cur == NULL) return; //终止条件
//单层逻辑
traversal(cur->left,vec);//左
traversal(cur->right,vec);//右
vec.push_back(cur ->val);//根
}
vector<int> preorderTraversal(TreeNode* root)
{
vector<int> result;
traversal(root,result);//将树传入生成数组
return result;
}
}迭代法
使用栈的方式实现
中序遍历 （中、右、左）
class Solution{
public：
vector<int> inorderTraversal(TreeNode* root){
vector<int> result; //存放
stack<TreeNode*>st;//创建一个栈
if(root != NULL) st.push(root)//根节点
while(!st.empty())//栈不为空
{
TreeNode* node = st.top();//指针指向栈顶部
if(node != NULL)//顶部不是空节点
{
st.pop();//将该节点弹出，避免重复操作，下面将右、中、左节点加入栈中
if(node ->right) st.push(node ->right);//添加右节点入栈（空节点不如栈）
st.push(node); // 添加根节点入栈
st.push(NULL) //中节点访问过，但是还没有处理，加入空节点为标记
if (node->left) st.push(node->left); // 添加左节点（空节点不入栈）
}else{ //只有遇到空节点的时候，才将下一个节点放进结果集
st.pop(); //将空节点弹出
node = st.top(); //重新取出栈中元素
st.pop();//弹出我们要记录的元素
result.push_back(node->val); //加入到容器中
}
}
return result;
}
}2、广度优先遍历
一层一层的遍历
层次遍历（迭代法）
遍历顺序 ： 根、左、右
分层 A / B G // C D H //E F
队列：先进先出
我们先把遍历每一层的元素先放到队列里面，然后放了之后就要开始准备下一次层的遍历。
弹出的时候存放它的子节点到队列中（这样的话就衔接上了，每一层元素都遍历了）
size记录每一层的节点数
个人理解：
极限一换一，顶罪，你爹出去了，儿子就得去队列里面顶罪
class Solution
{
public:
vector<int> bfs(TreeNode *root)//返回的是一个int的vector
{
vector<int>res;
queue<TreeNode *>q;//辅助队列
if(root==NULL)return res;//小事件结束标志
q.push(root);
while(!q.empty())
{
res.push_back(q.front()->val);
if(q.front()->left!=NULL)
{
q.push(q.front()->left);
}
if(q.front()->right!=NULL)
{
q.push(q.front()->right);
}
q.pop();//弹出第一个元素
}
return res;//只有最后才会执行这个
}
};代码随想录：
class Solution{
public:
vector<vector<int>> levelOrder(TreeNode* root){
queue<TreeNode*> que;
if(root != NULL) que.push(root);//节点存在，入队
vector<vector<int>> result;//存放出队的数据
while(!que.empty())//当队列不为空
{
int size = que.size();//记下队列元素个数
vector<int> vec;
for(int i = 0; i < size(); i++)
{
TreeNode* node = que.front();//指针指向出口
que.pop();//出队
vec.push_back(node->val);//将出队元素插入容器
if(node ->left) que.push(node -> left);//左儿子存在就进队
if(node ->right) que.push(node ->right);//右儿子存在，就进队
}
result.push_back(vec);
}
return result;//返回容器
}
};