leetcode 144 145 94二叉树的三种非递归遍历
2023-09-27 14:29:24 时间
leetcode144 非递归前序遍历
使用栈来模拟递归。
/**
* 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:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> my_stack;
if(root == nullptr) return result;
my_stack.push(root);//前序遍历是中左右,先处理一个中就是root
while(my_stack.empty() != 1)
{
TreeNode* my_node = my_stack.top();//提前中节点
my_stack.pop();
//中节点压入结果
result.push_back(my_node->val);
//之后将中节点的左右子节点放到栈里,作为未来的中节点
//压入栈的顺序和弹出栈是相反的,先遍历左再是右,所有先压入右再压入左
if(my_node->right != nullptr) my_stack.push(my_node->right);
if(my_node->left != nullptr) my_stack.push(my_node->left);
}
return result;
}
};
leetcode144 非递归后序遍历
使用栈来模拟递归。
核心逻辑和前序遍历一样,前序遍历是中左右,后序是中右左。
和前序代码类似,改变顺序。变成中右左。然后反转变成左右中
/**
* 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:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> my_stack;
if(root == nullptr) return result;
my_stack.push(root);
while(my_stack.empty() != 1)
{
TreeNode* my_node = my_stack.top();
my_stack.pop();
//和前序一样,但是变成中右左
result.push_back(my_node->val);
if(my_node->left != nullptr) my_stack.push(my_node->left);
if(my_node->right != nullptr) my_stack.push(my_node->right);
}
//反转,变成左右中
reverse (result.begin() , result.end());
return result;
}
};
leetcode94 非递归中序遍历
和前序后序的思路不一样。中序是左中右
先找到最左的叶子节点,然后开始输出。
输出左边的之后,从栈弹出一个,弹出的是输出左节点的中节点。
然后输出中节点,再到右节点。
找右节点有没有左子叶,不停循环
/**
* 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:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> my_stack;
if(root == nullptr) return result;
TreeNode* cur = root;
while(cur != nullptr || my_stack.empty() != 1)
{
if(cur != nullptr)//找到cur的最左叶子节点
{
my_stack.push(cur);//找的过程中所有的左节点都存起来
cur = cur->left;
}else//处理中节点和右节点
{
cur = my_stack.top();//输出栈里之前存的左节点 ,这时左节点看作成中间节点
my_stack.pop();
result.push_back(cur->val);
cur = cur->right;//然后找刚才输出左节点作为中间点时的右节点
}
}
return result;
}
};
相关文章
- leetCode 94.Binary Tree Inorder Traversal(二叉树中序遍历) 解题思路和方法
- Leetcode刷题记录:构建最大数二叉树
- 【Leetcode】102. 二叉树的层序遍历(中等)
- LeetCode搜索二叉树的练习
- 125、【回溯算法】leetcode ——47.全排列 II:visited去重(C++版本)
- 113、【树与二叉树】leetcode ——538. 把二叉搜索树转换为累加树:递增数组视角右中左遍历(C++版本)
- 109、【树与二叉树】leetcode ——701. 二叉搜索树中的插入操作:递归法+双指针迭代法(C++版本)
- 95、【树与二叉树】leetcode ——257. 二叉树的所有路径:递归法DFS/回溯法+迭代法DFS+层序遍历BFS(C++版本)
- 92、【树与二叉树】leetcode ——111. 二叉树的最小深度:层次遍历+先序DFS+后序DFS[子问题分解](C++版本)
- 88、【树与二叉树】leetcode ——226. 翻转二叉树:先中后序的递归与DFS非递归遍历+BFS层次遍历(C++版本)
- 【leetcode】106: 从中序与后序遍历序列构造二叉树
- 【Leetcode】105: 从前序与中序遍历序列构造二叉树
- [LeetCode] 971. Flip Binary Tree To Match Preorder Traversal 翻转二叉树以匹配先序遍历
- [LeetCode] 545. Boundary of Binary Tree 二叉树的边界
- [LeetCode] 394. Decode String 解码字符串
- [LeetCode] 314. Binary Tree Vertical Order Traversal 二叉树的竖直遍历
- [LeetCode] 244. Shortest Word Distance II 最短单词距离之二
- [LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal 由先序和中序遍历建立二叉树
- [LeetCode] 114. Flatten Binary Tree to Linked List 将二叉树展开成链表
- [LeetCode] 124. Binary Tree Maximum Path Sum 求二叉树的最大路径和
- LeetCode根据前序与中序、中序与后序,前序与后序遍历序列构建二叉树
- LeetCode二叉树中序遍历
- leetcode 145. Binary Tree Postorder Traversal 二叉树的后序遍历 (中等)
- leetcode 94. Binary Tree Inorder Traversal 二叉树的中序遍历(中等)
- leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal 从前序与中序遍历序列构造二叉树(中等)