代码随想录算法训练营第十四天 |二叉树理论基础、递归遍历、迭代遍历
2024-01-10 06:04:11
题目链接:
leetcode 144.二叉树的前序遍历
leetcode 194.二叉树的中序遍历
leetcode 145.二叉树的后序遍历
文章讲解:代码随想录二叉树理论基础、递归遍历、迭代遍历、统一迭代法
二叉树的遍历问题是很经典很基础的问题,这里只总结我学习过程中认为是重点关注的内容,相信对大家理解遍历方式以及自己动手写这个代码会有帮助!
我学习中只关注了递归法和统一迭代法,因为我认为不统一的迭代法性价比不高。
递归法
递归法很简单,注意递归的终止条件即可,递归也是写代码比较基础核心的思想,我认为掌握递归的核心要领就是掌握好终止条件,这个自己要好好体会。
以下代码对比来看。
递归法代码(前序遍历):
/**
* Definition for a binary tree node.
* 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) {}
* };
*/
class Solution {
public:
//递归法 实现函数
void preTraversal (TreeNode* node, vector<int>& result) {
//终止条件
if (node == nullptr) return ;
//前序遍历
result.push_back(node -> val);
preTraversal(node -> left, result);
preTraversal(node -> right, result);
return ;
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
preTraversal(root, result);
return result;
}
};
递归法代码(中序遍历):
/**
* Definition for a binary tree node.
* 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) {}
* };
*/
class Solution {
public:
//递归法 实现函数
void inTraversal (TreeNode* node, vector<int>& result) {
//终止条件
if (node == nullptr) return ;
//中序遍历
inTraversal(node -> left, result);
result.push_back(node -> val);
inTraversal(node -> right, result);
return ;
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
inTraversal(root, result);
return result;
}
};
递归法代码(后序遍历):
/**
* Definition for a binary tree node.
* 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) {}
* };
*/
class Solution {
public:
//递归法 实现函数
void postTraversal (TreeNode* node, vector<int>& result) {
//终止条件
if (node == nullptr) return ;
//后序遍历
postTraversal(node -> left, result);
postTraversal(node -> right, result);
result.push_back(node -> val);
return ;
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
postTraversal(root, result);
return result;
}
};
统一迭代法
思路就是用栈进行遍历,其实函数递归在底层也是用栈来实现的,当我们不用递归而是自己用栈的时候,对于二叉树遍历的核心解决方式并没有改变。
这个方法重点就是首先确认好访问节点和处理节点两个概念。
我们规定访问节点就是指当前指针走到了这个节点,不做处理操作,处理节点才是把当前指针走到的节点输出(在题目中就是放到结果容器中)。不好解释,自己好好体会一下
然后要注意的就是,我们如何利用栈遍历二叉树,首先栈式先入后出,假设要进行前序遍历,前序遍历式中左右,放入栈里的顺序就要是右左中,然后如何确定要处理节点了呢?那就是用空指针打标记。
每次循环访问栈顶元素时,如果遇到了空指针就说明要处理节点了,把空指针pop掉,再取栈顶元素,处理一下,再pop掉。
以下代码对比查看
统一迭代法(前序遍历):
//统一迭代法
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
//root先放进去
if (root != nullptr) st.push(root);
//思路是,按照顺序将对应节点放入栈中,注意要反着顺序放,因为栈是先入后出,然后给要处理的节点用空指针打标记
while (!st.empty()) {
//取出栈顶
TreeNode* cur = st.top();
if (cur != nullptr) {
//这里就是访问的节点(遍历到的节点),访问到就先把该节点从栈中pop掉
st.pop();
//然后通过向栈中放入元素决定,什么时候处理节点
//前序遍历原本是中左右,放入栈里就要放右左中
//确定有子节点才放入
if (cur -> right) st.push(cur -> right);
if (cur -> left) st.push(cur -> left);
//中指的是处理该节点,所以用空指针打标记
st.push(cur);
st.push(nullptr);
} else {
//走到这里说明遇到了标记,要处理标记前的节点了
st.pop();
cur = st.top();
result.push_back(cur -> val);
st.pop();
}
}
return result;
}
};
统一迭代法(中序遍历):
//统一迭代法
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
//root先放进去
if (root != nullptr) st.push(root);
//思路是,按照顺序将对应节点放入栈中,注意要反着顺序放,因为栈是先入后出,然后给要处理的节点用空指针打标记
while (!st.empty()) {
//取出栈顶
TreeNode* cur = st.top();
if (cur != nullptr) {
//这里就是访问的节点(遍历到的节点),访问到就先把该节点从栈中pop掉
st.pop();
//然后通过向栈中放入元素决定,什么时候处理节点
//中序遍历原本是左中右,放入栈里就要放右中左
//确定有子节点才放入
if (cur -> right) st.push(cur -> right);
//中指的是处理该节点,所以用空指针打标记
st.push(cur);
st.push(nullptr);
if (cur -> left) st.push(cur -> left);
} else {
//走到这里说明遇到了标记,要处理标记前的节点了
st.pop();
cur = st.top();
result.push_back(cur -> val);
st.pop();
}
}
return result;
}
};
统一迭代法(后序遍历):
//统一迭代法
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
//root先放进去
if (root != nullptr) st.push(root);
//思路是,按照顺序将对应节点放入栈中,注意要反着顺序放,因为栈是先入后出,然后给要处理的节点用空指针打标记
while (!st.empty()) {
//取出栈顶
TreeNode* cur = st.top();
if (cur != nullptr) {
//这里就是访问的节点(遍历到的节点),访问到就先把该节点从栈中pop掉
st.pop();
//然后通过向栈中放入元素决定,什么时候处理节点
//后序遍历原本是左右中,放入栈里就要放中右左
//中指的是处理该节点,所以用空指针打标记
st.push(cur);
st.push(nullptr);
//确定有子节点才放入
if (cur -> right) st.push(cur -> right);
if (cur -> left) st.push(cur -> left);
} else {
//走到这里说明遇到了标记,要处理标记前的节点了
st.pop();
cur = st.top();
result.push_back(cur -> val);
st.pop();
}
}
return result;
}
};
文章来源:https://blog.csdn.net/Tong_1024_/article/details/135478440
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!