🌏个人博客主页：心.c
前言：最近学习了二叉树，和大家分享一下我的理解和感悟，希望对大家有所帮助，话不多说，开整！！！
🔥🔥🔥专题文章：二叉树
😽感谢大家的点赞👍收藏⭐️评论✍您的一键三连是我更新的动力 💓
目录
概念：
二叉树的结构：
图解：
结构体创建：
二叉树的分类：
满二叉树
完全二叉树：
平衡二叉树
二叉搜索树
二叉树遍历：
二叉树遍历方式：
递归遍历演示：
前序遍历：
中序遍历：
后续遍历：
迭代遍历演示（栈）：
前序遍历：
中序遍历：
后续遍历：
概念：
二叉树是一种每个节点最多有两个子节点的数据结构。通常，这两个子节点被称为左子节点和右子节点。
二叉树的结构：
图解：
结构体创建：
// 二叉树节点结构体
struct TreeNode {int val; // 节点值TreeNode* left; // 指向左子节点的指针TreeNode* right; // 指向右子节点的指针// 默认构造函数TreeNode() : val(0), left(nullptr), right(nullptr) {}// 带值的构造函数TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}// 带左右子节点的构造函数TreeNode(int x, TreeNode* left, TreeNode* right): val(x), left(left), right(right) {}
};二叉树的分类：
满二叉树
每个节点都有0或2个子节点的二叉树。满二叉树的每一层都完全填满。
完全二叉树：
一个二叉树，除了最底层外，每层的节点都被填满，且最底层的节点都靠左对齐。
平衡二叉树：
一棵二叉树，任意节点的两个子树的高度差不超过1。常见的平衡二叉树包括 AVL 树和红黑树。
二叉搜索树：
一种特定类型的二叉树，每个节点的左子树的值都小于节点的值，而右子树的值都大于节点的值。这使得搜索、插入和删除操作都具有较高的效率
二叉树遍历：
二叉树遍历方式：
前序遍历：
- 先遍历中间节点
- 然后遍历左孩子
- 最后遍历右孩子
中序遍历：
- 先遍历左孩子
- 再遍历中间节点
- 追回遍历右孩子
后续遍历：
- 先遍历左孩子
- 再遍历右孩子
- 最后遍历中间节点
递归遍历演示：
相关题目链接：
1. 前序遍历
2. 中序遍历
3. 后序遍历
前序遍历：
class Solution {
public:void postorder(TreeNode* root, vector<int>& res) {if (!root) {return;}res.push_back(root->val);postorder(root->left, res);postorder(root->right, res);}vector<int> postorderTraversal(TreeNode* root) {vector<int> res;postorder(root, res);return res;}
};中序遍历：
class Solution {
public:void postorder(TreeNode* root, vector<int>& res) {if (!root) {return;}postorder(root->left, res);res.push_back(root->val);postorder(root->right, res);}vector<int> postorderTraversal(TreeNode* root) {vector<int> res;postorder(root, res);return res;}
};后续遍历：
class Solution {
public:void postorder(TreeNode* root, vector<int>& res) {if (!root) {return;}postorder(root->left, res);postorder(root->right, res);res.push_back(root->val);}vector<int> postorderTraversal(TreeNode* root) {vector<int> res;postorder(root, res);return res;}
};迭代遍历演示（栈）：
前序遍历：
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> stack;vector<int> result;if (root == nullptr)return result;stack.push(root);while (!stack.empty()) {root = stack.top();stack.pop();result.push_back(root->val);if (root->right) {stack.push(root->right);}if (root->left) {stack.push(root->left);}}return result;}
};中序遍历：
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> stack;TreeNode* cur = root;while (cur != nullptr || !stack.empty()) {if (cur != nullptr) {stack.push(cur);cur = cur->left;} else {cur = stack.top();stack.pop();result.push_back(cur->val);cur = cur->right;}}return result;}
};后续遍历：
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> stack;vector<int> result;if (root == nullptr)return result;stack.push(root);while (!stack.empty()) {root = stack.top();stack.pop();result.push_back(root->val);if (root->left) {stack.push(root->left);}if (root->right) {stack.push(root->right);}}reverse(result.begin(), result.end());return result;}
};这里就分享完了，感谢大家的观看
