二叉树的前序遍历
https://leetcode.cn/problems/binary-tree-preorder-traversal/
递归
class Solution {
public:
vector<int> res;
vector<int> preorderTraversal(TreeNode* root) {
dfs(root);
return res;
}
void dfs(TreeNode* root) {
if (!root)
return;
res.push_back(root->val);
dfs(root->left);
dfs(root->right);
}
};
迭代
/*
前序迭代基本等同于bfs模板,但注意是使用栈记录待访问节点
先对res记录根值,再按照右节点-左节点的次序入栈,这样出栈顺序就是左右
*/
class Solution {
public:
vector<int> res;
vector<int> preorderTraversal(TreeNode* root) {
if (!root)
return res;
stack<TreeNode*> stk;
stk.push(root);
while (stk.size())
{
auto tmp = stk.top();
stk.pop();
res.push_back(tmp->val); // 体现前序
if (tmp->right)
stk.push(tmp->right);
if (tmp->left)
stk.push(tmp->left); // 先右后左
}
return res;
}
};
二叉树的中序遍历
https://leetcode.cn/problems/binary-tree-inorder-traversal/
递归
class Solution {
public:
vector<int> res;
vector<int> inorderTraversal(TreeNode* root) {
dfs(root);
return res;
}
void dfs(TreeNode* root) {
if (!root)
return;
dfs(root->left);
res.push_back(root->val);
dfs(root->right);
}
};
迭代1,模板
/*
对于中序遍历,同样需要使用栈来模拟进出,但是步骤差异很大:
首先需要迭代所有最左节点,再根再右
将所有左下角的节点入栈,再依次出栈,记录res后再访问右节点
*/
class Solution {
public:
vector<int> res;
vector<int> inorderTraversal(TreeNode* root) {
if (!root)
return res;
stack<TreeNode*> stk;
while (root || stk.size()) // 当root访问完毕且栈里没元素时,循环结束
{
while (root) // 入栈所有左侧的左节点,直到为空
{
stk.push(root);
root = root->left;
}
root = stk.top(); // 第一个root为左叶子节点
stk.pop(); // 循环中将左节点依次出栈
res.push_back(root->val); // 体现中序
root = root->right; // 再访问右子树
}
return res;
}
};
迭代2,使用哈希表去重
/*
使用哈希表跳过已访问节点,可以避免出栈后再次寻找左节点进入死循环
*/
class Solution {
public:
vector<int> res;
vector<int> inorderTraversal(TreeNode* root) {
if (!root)
return res;
stack<TreeNode*> stk;
stk.push(root);
unordered_map<TreeNode*, bool> hash;
hash[root] = true; // 标记为已使用
while (stk.size())
{
root = stk.top(); // 注意和层次遍历的区别就是出栈(队)时机
while (root->left) // 同样将所有左节点入栈,注意root落在叶子节点上
{
if (hash[root->left]) // 二手达咩
break;
stk.push(root->left);
hash[root->left] = true;
root = root->left;
}
stk.pop(); // 不能在上面先出栈,因为会丢失根节点
res.push_back(root->val); // 体现中序
if (root->right)
{
stk.push(root->right);
root = root->right;
}
}
return res;
}
};
二叉树的后序遍历
https://leetcode.cn/problems/binary-tree-postorder-traversal/
递归
class Solution {
public:
vector<int> res;
vector<int> postorderTraversal(TreeNode* root) {
dfs(root);
return res;
}
void dfs(TreeNode* root) {
if (!root)
return;
dfs(root->left);
dfs(root->right);
res.push_back(root->val);
}
};
迭代
/*
以前序的基础改造后序迭代法
前序的遍历是中-左右,入栈次序是右-左
翻转后续的遍历是中-右左-翻转,所以入栈次序变为左-右
*/
class Solution {
public:
vector<int> res;
vector<int> postorderTraversal(TreeNode* root) {
if (!root)
return res;
stack<TreeNode*> stk;
stk.push(root);
while (stk.size())
{
auto tmp = stk.top();
stk.pop();
res.push_back(tmp->val); // 体现前序(翻转前)
if (tmp->left)
stk.push(tmp->left);
if (tmp->right)
stk.push(tmp->right); // 先左后右
}
reverse(res.begin(), res.end()); // 翻转
return res;
}
};
你好,我是AilingGu
我测你码