当前位置：首页 > news >正文

力扣日记11.5-【二叉树篇】二叉树的迭代遍历

news 来源：原创 2024/7/6 15:16:46

力扣日记：【二叉树篇】二叉树的迭代遍历

日期：2023.11.5
参考：代码随想录、力扣

144. 二叉树的前序遍历

题目描述

难度：简单

给你二叉树的根节点 root ，返回它节点值的前序遍历。

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

题解

cpp ver

/*** 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;traversal(root, result);return result;}void traversal(TreeNode* cur, vector<int>& vec) {// 前序遍历：中左右if (cur == NULL) return;vec.push_back(cur->val);traversal(cur->left, vec);traversal(cur->right, vec);}
};

复杂度

时间复杂度：
空间复杂度：

94. 二叉树的中序遍历

题目描述

难度：简单

给定一个二叉树的根节点 root ，返回它的中序遍历。

题解

/*** 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) {// 中序遍历：左中右// 对于中序遍历，访问和处理并不是同步进行的。而是先访问到最底层的左节点，再开始处理（放进result数组）// 使用 cur 指针 先进行访问（遍历）vector<int> result;if (root == NULL) return result;stack<TreeNode*> st;TreeNode* cur = root;while (cur != NULL || !st.empty()) {if (cur != NULL) { // 指针访问节点，先遍历到最底层st.push(cur);   // 将cur入栈cur = cur->left;    // 左} else { // 处理cur = st.top();   // 中 (处理：放入result数组)st.pop();result.push_back(cur->val);cur = cur->right;   // 右 (如果右节点不为空，则在下次循环把右节点入栈；否则从栈中弹出顶部节点)}}return result;}
};

复杂度

时间复杂度：
空间复杂度：

145. 二叉树的后序遍历

题目描述

难度：简单

给你一棵二叉树的根节点 root ，返回其节点值的后序遍历。

题解

/*** 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) {// 后序遍历：左右中// 相对于前序遍历：前序遍历为 中左右 -> 把前序遍历的迭代写法的左右部分互换 -> 则为 中右左 // -> 再把result 数组反向 -> 左右中（后序遍历）vector<int> result;if (root == NULL) return result;stack<TreeNode*> st;// 先放入根节点st.push(root);while (!st.empty()) {// 中TreeNode* cur = st.top();st.pop();result.push_back(cur->val);if (cur->left != NULL) st.push(cur->left);    // 与前序遍历相反：左节点先入栈（空节点不入栈）if (cur->right != NULL)  st.push(cur->right);}// 此时result顺序为 中右左// 反向reverse(result.begin(), result.end());return result;}
};