【每日刷题】Day130
【每日刷题】Day130
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 144. 二叉树的前序遍历 - 力扣（LeetCode）
2. 94. 二叉树的中序遍历 - 力扣（LeetCode）
3. 145. 二叉树的后序遍历 - 力扣（LeetCode）
1. 144. 二叉树的前序遍历 - 力扣（LeetCode）
//思路：非递归。
//递归进行遍历二叉树非常简单，但是非递归就要麻烦很多了。
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root)
{
vector<int> ans;
stack<TreeNode*> st;//存放节点的栈
TreeNode* cur = root;
while(cur||!st.empty())
{
while(cur)//一路往左遍历到空
{
ans.push_back(cur->val);
st.push(cur);
cur = cur->left;
}
TreeNode* tmp = st.top();//获取栈顶节点，也就是返回上一个节点
st.pop();
cur = tmp->right;//去右子树继续重复上述过程
}
return ans;
}
};
2. 94. 二叉树的中序遍历 - 力扣（LeetCode）
//思路：非递归。
//基本思路与 "前序遍历" 的非递归基本一致。唯一的区别在于访问根节点值的时机。
// "前序遍历" 中 cur 在遍历的同时就记录了根节点的值。而中序遍历我们需要在 cur 往左遍历到空后，记录根节点的值。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root)
{
vector<int> ans;
stack<TreeNode*> st;
TreeNode* cur = root;
while(cur||!st.empty())
{
while(cur)//往左遍历到空，并将节点放入栈中
{
st.push(cur);
cur = cur->left;
}
ans.push_back(st.top()->val);//记录根节点值
TreeNode* tmp = st.top();
st.pop();
cur = tmp->right;
}
return ans;
}
};
3. 145. 二叉树的后序遍历 - 力扣（LeetCode）
//思路：非递归。
//思路大体上还是相同的，但是细节的处理多了很多。
//首先，还是让 cur 往左遍历到空。随后 tmp 获取栈顶元素，此时分为三种情况：
//① 如果 tmp->right 为空，说明此时 tmp 为叶子节点，将值放入 ans 数组中
//② 如果 tmp->right 不为空，说明还有右子树，cur 去到 tmp->right
//③ 这种情况最麻烦：tmp->right 不为空，但是 tmp->right 的节点的值我们已经存储过了，从 tmp->right 回到根节点，此时我们也是需要记录 tmp->val 的。
//但是根据我们①、②点的逻辑是没法做到的，并且会陷入死循环，因为会一直走 cur = tmp->right 的逻辑
//因此这里我们需要用一个变量 prev 来记录存储过的 tmp->right 节点
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root)
{
vector<int> ans;
stack<TreeNode*> st;
TreeNode* cur = root;
TreeNode* prev = nullptr;
while(cur||!st.empty())
{
while(cur)
{
st.push(cur);
cur = cur->left;
}
TreeNode* tmp = st.top();
//前面思路相同
if(!tmp->right||tmp->right==prev)//如果tmp->right==prev，说明 tmp->right 已经记录过（也可以理解为从tmp->right 回来了），此时 tmp->val也要记录，因为左右子树都遍历完了
{
ans.push_back(tmp->val);
st.pop();
prev = tmp;//使用 prev 记录存储过的 tmp->right
}
else cur = tmp->right;
}
return ans;
}
};