二叉树遍历|二叉树递归遍历、二叉树迭代遍历
二叉树递归遍历
自己审题思路
二叉树遍历使用递归思想
看完代码随想录题解后的收获
1、二叉树迭代实现思想
2、递归写法的套路和思路
a、确定递归函数的参数和返回值
b、确定终止条件
c、确定单层递归的逻辑
代码(前序)：
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;
}
};
参考详解
二叉树迭代遍历
自己审题思路
迭代使用栈来模拟递归的调用
看完代码随想录题解后的收获
具体的实现思路和一些不同的实现思路
代码（前序1）：
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> st;
if (root == nullptr) return ans;
TreeNode* cur = root;
while(!st.empty() || cur != nullptr) { // 一直走到最左边，然后返回
while(cur != nullptr) {
ans.push_back(cur->val);
st.push(cur);
cur = cur->left;
}
cur = st.top();
st.pop();
cur = cur->right;
}
return ans;
}
};
代码（前序2）：
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
if (root == NULL) return result;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top(); // 中
st.pop();
result.push_back(node->val);
if (node->right) st.push(node->right); // 右（空节点不入栈）
if (node->left) st.push(node->left); // 左（空节点不入栈）
}
/* 也可以这么处理
while (!st.empty()) {
TreeNode* node = st.top(); // 中
st.pop();
if(ndoe == nullptr) continue;
result.push_back(node->val);
st.push(node->right); // 右
st.push(node->left); // 左
}*/
return result;
}
};
代码（中序1）：
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> st;
if (root == nullptr) return ans;
TreeNode* cur = root;
while(!st.empty() || cur != nullptr) { //一直走到最左边，然后弹出元素处理
while (cur != nullptr) {
st.push(cur);
cur = cur->left;
}
cur = st.top();
st.pop();
ans.push_back(cur->val);
cur = cur->right;
}
return ans;
}
};
代码（中序2）：
class Solution {
public:
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(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
st.pop();
result.push_back(cur->val); // 中
cur = cur->right; // 右
}
}
return result;
}
};
代码（后序1）：
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> st;
if (root == NULL) return ans;
TreeNode* cur = root;
TreeNode* pre = NULL;//标志位
while (!st.empty() || cur != NULL) {
while (cur != NULL) { //遍历到最左边
st.push(cur);
cur = cur->left;
}
cur = st.top();//获取栈顶元素，用来下一步处理
st.pop(); //遍历到最左边了弹出栈，
if (cur->right == NULL || cur->right == pre) { //该节点没有右孩子 || 右孩子遍历过了
ans.push_back(cur->val);
pre = cur; // 标记这个节点访问过了
cur = NULL; // 避免重复访问左孩子
} else { // 存在右孩子 && 右孩子没遍历过
st.push(cur);// 将弹出的节点重新压进栈
cur = cur->right; // 遍历右孩子
}
}
return ans;
}
};
代码（后序2）：
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
if (root == NULL) return result;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
result.push_back(node->val);
if (node->left) st.push(node->left); // 相对于前序遍历，这更改一下入栈顺序 （空节点不入栈）
if (node->right) st.push(node->right); // 空节点不入栈
}
reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
return result;
}
};
while(!st.empty() || cur != nullptr) {中的cur != nullptr是为了第一次能够进入循环 （第一次栈为空）
中序遍历的两个代码循环条件其实是一致的，都是一直遍历到最左边再处理
参考详解
今日感悟
主要是理解二叉树结构和递归的过程
