[代码随想录13]二叉树的基本结构，递归法和迭代法，同意迭代，层序遍历
前言
什么是二叉树？类比于生活中的大树小树，但是他只能有两个分叉，所以我们就有两种特殊情况，满二叉树和完全二叉树，顾名思义，满二叉树就是树枝都长满了，完全二叉树就是按照顺序来叶子结点还差一点，接着，对于“长的好的”树形结构（有序的二叉树，左边节点都小于右边节点），成为二叉搜索树，俗称SB树，有序的目的就是为了查找的效率提升，但是我们查找数据是查找二叉树的高度次，对高度严格平衡的，左右子树相差一个高度的成为平衡二叉搜索树，AVL树，但是这个太严格了，花费很多时间在旋转调节上，我们又提出了红黑树，达到相对平衡的效果，这也就是map和set的底层数据结构。
外话：
在之后我们会提出哈希表结构，那个是unordered_map和unordered_set的结构，查找会更快O(1),采用映射到特定方法去。相当于我们出去吃饭，我们有了预定，我们到了直接去我们的地方就行，不需要在从头区找位置。但是会消耗空间。
题目链接
一、递归
主要思路就是，借助一个函数去完成递归的过程。 这个函数需要传入根结点和结果集，然后有一个终止条件就可以了。接下来就是传入的概念，前序就是中左右，中序就是左中右，后续就行左右中，看的是中间节点的位置来判断。
//前序
void traversal(TreeNode* cur,vector<int>& vec){
if(cur==nullptr)return;
vec.push_back(cur->val);
traversal(cur->left,vec);
traversal(cur->right,vec);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
traversal(root,res);
return res;
}
//中序
void traversal(TreeNode* cur,vector<int>& vec){
if(cur==nullptr)return;
traversal(cur->left,vec);
vec.push_back(cur->val);
traversal(cur->right,vec);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
traversal(root,res);
return res;
}
//后序
void traversal(TreeNode* cur,vector<int>& vec){
if(cur==nullptr)return;
traversal(cur->left,vec);
traversal(cur->right,vec);
vec.push_back(cur->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
traversal(root,res);
return res;
}二、迭代
前序：思路就是借助辅助栈，先入根节点，然后出根节点，入根节点的左右，在分裂。插入数据。
中序：先全进左边集合的辅助栈，然后弹出遍历。
后序：思路就是借助辅助栈，和前序一样，先入根节点，然后出根节点，入根节点的左右，在分裂。插入数据。先入左后右，因为最后需要翻转一下。
//前序
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*>st;
vector<int> res;
if(root==nullptr)return res;
st.push(root);
while(!st.empty()){
TreeNode*node=st.top();//中
st.pop();
res.push_back(node->val);
if(node->right)st.push(node->right);
if(node->left)st.push(node->left);
}
return res;
}
//中序
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
TreeNode* cur = root;
while (cur != NULL || !st.empty()) {
if (cur != NULL) {
st.push(cur);
cur = cur->left;
} else {
cur = st.top();
st.pop();
result.push_back(cur->val); // 中
cur = cur->right;// 右
}
}
return result;
//后序
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*>st;
vector<int> res;
if(root==nullptr)return res;
st.push(root);
while(!st.empty()){
TreeNode*node=st.top();//中
st.pop();
res.push_back(node->val);
if(node->left)st.push(node->left);
if(node->right)st.push(node->right);
}
reverse(res.begin(),res.end());
return res;
}
三、统一迭代
同意迭代的思路:
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;
}
四、层序遍历
思路：
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> q;
int levelSize=0;
if(root)
{
q.push(root);
levelSize=1;
}
vector<vector<int>> vv;
while(!q.empty())
{
//一层一层出
vector<int> v;
while(levelSize--)
{
TreeNode* front=q.front();
q.pop();
v.push_back(front->val);
if(front->left)
{
q.push(front->left);
}
if(front->right)
{
q.push(front->right);
}
}
vv.push_back(v);
levelSize=q.size();
}
return vv;
}原文地址：https://blog.csdn.net/m0_63191032/article/details/144383859
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！