树：
基本概念：数据结构与算法-树_Evan_L的博客-CSDN博客_数据结构与算法 树
树的算法求解本质上：是递归运算
树的遍历：前序：根左右；中序：左根右；后序：左右根
1： 二叉树的中序遍历
思路： 递归、 左根右
class Solution {
public:
vector inorderTraversal(TreeNode* root) {
// 用数组来存储树的元素
vector res;
backtreak(root, res); // 建立一个递归函数 去
return res;
}
void backtreak(TreeNode* root, vector& res)
{
if (root == nullptr) // 递归结束
return;
if (root->left)
backtreak(root->left, res); // 左子树递归
res.push_back(root->val); // 当前根节点存放
if (root->right)
backtreak(root->right, res); // 左子树递归
return;
}
};
2: 二叉树的前序遍历
思路
class Solution {
public:
vector preorderTraversal(TreeNode* root) {
vector res;
// 递归求解
backtrack(root, res);
return res;
}
void backtrack(TreeNode* root, vector& res)
{
if (root == nullptr)
return;
res.push_back(root->val); // 将当前根节点存放
if (root->left) // 左子树递归
backtrack(root->left, res);
if (root->right) // 右子树递归
backtrack(root->right, res);
return;
}
};
3: 二叉树的后续遍历
class Solution {
public:
vector postorderTraversal(TreeNode* root) {
vector res;
backtrack(root, res);
return res;
}
void backtrack(TreeNode* root, vector& res)
{
if (root == nullptr)
return;
if (root->left)
backtrack(root->left, res);
if (root->right)
backtrack(root->right, res);
res.push_back(root->val);
return;
}
};
4: 二叉树的层序遍历
思路： 队列构造
class Solution {
public:
vector> levelOrder(TreeNode* root) {
vector> res;
if (root == nullptr) return res;
// 利用队列先进先出特点存放每一层的树的节点
queue q;
q.push(root);
while (!q.empty()) { // 队列不为空 说明还有树的节点
int curLevelNodeNum = q.size(); // 当前层的节点总数
vector cur_res; // 存储当前层节点值
for (int i = 0; i < curLevelNodeNum; i++) { // for循环让该层所有节点入对列
auto node = q.front();
q.pop(); // 出队列
cur_res.push_back(node->val);
if (node->left) q.push(node->left); // 左节点入队列
if (node->right) q.push(node->right); // 右节点入队列
}
res.push_back(cur_res); // 将当前层的结果赋值给res
}
return res;
}
};
5： 判断是否为平衡二叉树
（平衡： 任意一个子树节点高度差的绝对值<=1）(树的高度概念)
思路： 使用递归，自顶向下判断每个左右子树是否平衡
求解高度： 使用递归，自顶向下求当前子树的高度。
class Solution {
public:
bool isBalanced(TreeNode* root) {
// 递归结束条件
if (root == nullptr)
return true;
// 递归去判断每一层左右子树是否满足平衡 isBalance递归调用
return abs(height(root->left)-height(root->right)) <= 1&& isBalanced(root->left) && isBalanced(root->right);
}
// 求当前节点的高度（节点本身的高度是1） 队规求解
int height(TreeNode* root)
{
// 递归结束条件
if (root == nullptr)
return 0;
// +1 是包括节点本身 求左右子树最大的一个高度
// 自顶向下 递归的去求解高度 每递归一层 树的高度+1 左右子树,使用max只去考虑一种
int cur_node_height = max(height(root->left),height(root->right)) + 1;
return cur_node_height;
}
};
6： 求解二叉树的最大深度
思路： 递归 自顶向下去当前节点的深度
class Solution {
public:
int maxDepth(TreeNode* root) {
// 自顶向下 递归求解
if (root == nullptr)
return 0;
// 树的高度（深度）包括节点本身（+1）
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
7: 前序遍历非递归实现
思路： 利用栈实现当前节点（一定是左右子树的父节点）入栈和出栈。根左右的遍历顺序。
class Solution {
public:
vector preorderTraversal(TreeNode* root) {
// 非递归求解二叉树前序遍历
// 使用栈数据结构来遍历二叉树
stack s;
vector res;
if (root == nullptr) return res;
// 将根节点压入栈;
TreeNode* cur_node = root;
// 循环变量栈，访问二叉树
while (cur_node != nullptr || !s.empty()) {
// 判断当前节点是否存在
if (cur_node != nullptr) {
s.push(cur_node); // 当前节点入栈
res.push_back(cur_node->val); //获取当前节点的值
cur_node = cur_node->left; //遍历左子树,当前节点更新
} else {
// 迭代的当前节点为空
// 获取当前的节点的父节点，并且出栈父节点
cur_node = s.top();
s.pop(); // 出栈
cur_node = cur_node->right;//遍历右子树,当前节点更新
}
}
return res;
}
};
8: 非递归实现二叉树的中序遍历
class Solution {
public:
vector inorderTraversal(TreeNode* root) {
// 用栈实现二叉树的非递归中序遍历
vector res;
if (root == nullptr)
return res;
// 定义一个游标来指向当前的节点
TreeNode* cur_node;
cur_node = root;
// 定义一个栈来访问存放当前父节点
stack s;
while(cur_node != nullptr || !s.empty()) {
// 当前(父)节点非空
if (cur_node != nullptr) {
s.push(cur_node); // 入栈
cur_node = cur_node->left; // 左子树遍历 更新当前节点
} else {
// 当前节点为空
cur_node = s.top(); // 获取当前父节点
s.pop(); // 出栈
res.push_back(cur_node->val); // 左根右的遍历 所有在这里
cur_node = cur_node->right; // 右子树遍历 更新当前节点
}
}
return res;
}
};
9: 二叉树剪枝
思路：（1) dfs 递归判断当前节点作为根节点的子树是否满足剪枝条件
（2）剪枝条件： 当前子树为空；当前左右子树没有包含1的节点；
class Solution {
public:
TreeNode* pruneTree(TreeNode* root) {
if (root == nullptr)
return nullptr;
if (dfs(root))
return root;
return nullptr;
}
// 深度优先搜索算法 以当前节点为子树的根节点 只有子树包括本身有1个等于1的这个根节点就不能删
bool dfs(TreeNode* root)
{
// 当前节点为空 当然就不包括等于1的节点
if (root == nullptr) {
return false;
}
// 深度遍历 左子树 和 右子树
bool left_ = dfs(root->left);
bool right_ = dfs(root->right);
// 符合剪枝条件的
if (left_ == false) {
root->left = nullptr; // 左子树置空 剪枝
}
if (right_ == false) {
root->right = nullptr; // 右子树置空 剪枝
}
// 只要都是false 才会返回false. (当前子树根节点为不等于1 左右子树都为false)
return root->val == 1 || left_ || right_;
}
};
10: 合并二叉树
（1）dfs遍历
（2）
两个二叉树的对应节点可能存在以下三种情况，对于每种情况使用不同的合并方式。
如果两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空；
如果两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点；
如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和，此时需要显性合并两个节点。
对一个节点进行合并之后，还要对该节点的左右子树分别进行合并。这是一个递归的过程
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
// dfs (一层层遍历)
// 只要有1方为空 就选取另一方
if (root1 == nullptr)
return root2;
else if (root2 == nullptr)
return root1;
// 两个子树都不为空
TreeNode* merged = new TreeNode(root1->val + root2->val); // 创建一个节点来存放 合并生成一个新的节点
merged->left = mergeTrees(root1->left, root2->left);// 左子树递归生成
merged->right = mergeTrees(root1->right, root2->right); // 右子树递归生成
return merged;
}
};
