LeetCode:经典题之144、94、145、102题解及延伸|二叉树的遍历|前中后层序遍历|Morris算法
系列目录
88.合并两个有序数组
52.螺旋数组
567.字符串的排列
643.子数组最大平均数
150.逆波兰表达式
61.旋转链表
160.相交链表
83.删除排序链表中的重复元素
389.找不同
1491.去掉最低工资和最高工资后的工资平均值
896.单调序列
206.反转链表
92.反转链表II
141.环形链表
142.环型链表
21.合并两个有序列表
24.两辆交换链表中的节点
876.链表的中间节点
143. 重排链表
2.两数相加
445.两数相加II
目录
- 系列目录
- 前言
- Morris遍历
- 简介
- 代码实现
- 144.二叉树的前序遍历
- 94.二叉树的中序遍历
- 145.二叉树的后序遍历
- 102.二叉树的层序遍历
前言
方法都是类似的~
递归是隐式调用栈(递归栈,无需手动实现),迭代是显式调用栈
Morris遍历
简介
Morris遍历是一种高效的二叉树遍历算法,其显著特点是能在不使用额外的栈或队列,而是利用树大量的空闲指针完成遍历,空间复杂度为O(1)
1. 遍历思路
1、开始时 cur = root,cur为空时过程停止
2、若cur无左树,cur向右移动
3、若cur有左树,找到左树最右节点mostRight
a.若mostRight的右指针指向空,让其指向cur,cur向左移动
b.若mostRight的右指针指向cur,让其指向空,cur向右移动
举例:
/** a
* / \
* b e
* / \ / \
* c d f g
*
* Morris = [a, b, c, b, d, a, e, f, e, g]
/
2. 类型转换
Morris遍历可以实现前序、中序和后序遍历
- 前序遍历:在第一次访问节点时,输出节点的值,然后进行左子树的遍历
- 中序遍历:在第二次访问节点时(即mostRight的右指针指向当前节点时),输出节点的值,然后进行右子树的遍历
- 后序遍历:后序遍历的实现相对复杂,需要在遍历过程中记录左子树最右分支的路径,并在回溯时逆序输出
3. 优缺点
- 优点:Morris遍历的空间复杂度为O(1),比使用栈或递归的遍历算法更高效
此外,Morris遍历不会占用额外的内存空间,对于内存受限的环境非常友好 - 缺点:Morris遍历会修改原始树的结构,需要在遍历完成后还原 此外,Morris遍历的实现相对复杂,需要理解其背后的思想和原理
代码实现
// Morris遍历
public:vector<int> void morris(TreeNode *root) {TreeNode *cur = root;TreeNode *mostRight = nullptr;while (cur != cullptr) {mostRight = cur->left;// cur 有左树if (mostRight != nullptr) {// 最右节点不为空 且 不为curwhile (mostRight->right != nullptr && mostRight->right != cur){most = most->right;}// 第一次到达// cur左子树的 最右节点mostRight的右指针指向空// cur 向右移动if (mostRight == nullptr) {mostRight->right = cur;cur = cur->left;continue;}// 第二次到达// 此时cur左子树的 最右节点mostRight的右指针指向cur// cur 向左移动else {// 恢复mostRight->right = nullptr;// cur = cur->right;}}// cur 无子树,向右移动cur = cur->right;}
};
Morris遍历模板
public: vector<int> marris(TreeNode *root) {TreeNode *cur = root;TreeNode *mostRight = nullptr;while (cur != nullptr) {mostRight = cur->left;if (mostRight != nullptr) {while (mostRight->right != nullptr && mostRight->right != cur) {mostRight = mostRight->right;}if (mostRight == nullptr) {mostRight->right = cur;cur = cur->left;continue;} else {mostRight->right = nullptr;// cur = cur->right}} cur = cur->right;}
};
Morris遍历加工出前序
测试链接
/*** 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) {// 修改Ivector<int> res;if (root == nullptr)return res;TreeNode *cur = root;TreeNode *mostRight = nullptr;while (cur != nullptr) {mostRight = cur->left;// cur 有左树if (mostRight != nullptr) {// 最右节点不为空 且 不为curwhile (mostRight->right != nullptr && mostRight->right != cur){mostRight = mostRight->right;}// 第一次到达// cur左子树的 最右节点mostRight的右指针指向空// cur 向右移动if (mostRight->right == nullptr) {// 对于有左子树的节点——第一次收集// 修改II// emplace_back()也可res.push_back(cur->val);mostRight->right = cur;cur = cur->left;// 别忘了 continuecontinue;}// 第二次到达// cur左子树的 最右节点mostRight的右指针指向cur// cur 向左移动else {// 恢复mostRight->right = nullptr;// cur = cur->right;}} else {// 对于没有左子树的节点——直接收集// 修改IIIres.emplace_back(cur->val);}// cur 无子树,向右移动cur = cur->right;}// 修改IV// 别忘了 修改时在最后返回resreturn res;}
};
Morris遍历加工出中序
测试链接
写法一 一般写法
/*** 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) {// 修改Ivector<int> ans;if (root == nullptr)return ans;TreeNode *cur = root, *mostRight = nullptr;while (cur != nullptr) {mostRight = cur->left;if (mostRight != nullptr) {while (mostRight->right != nullptr && mostRight->right != cur)mostRight = mostRight->right;if (mostRight->right == nullptr) {mostRight->right = cur;cur = cur->left;continue;} else {// 修改IIans.push_back(cur->val);mostRight->right = nullptr;} } else {// 修改IIIans.push_back(cur->val);}cur = cur->right; }// 修改IVreturn ans;}
};
写法二 简略写法
/*** 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) {// 修改Ivector<int> ans;if (root == nullptr)return ans;TreeNode *cur = root, *mostRight = nullptr;while (cur != nullptr) {mostRight = cur->left;if (mostRight != nullptr) {while (mostRight->right != nullptr && mostRight->right != cur)mostRight = mostRight->right;if (mostRight->right == nullptr) {mostRight->right = cur;cur = cur->left;continue;} else {mostRight->right = nullptr;} } // 修改II// 无左树——只被遍历1次;有左树——第2次遍历 都会经过这里ans.push_back(cur->val);cur = cur->right; }// 修改IIIreturn ans;}
};
144.二叉树的前序遍历
🌟递归
原题链接
C++
若未特殊标明,以下题解均写用C++
方法一 递归
/*** 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:// 注意引用符void preorder(TreeNode* root, vector<int> &res) {if (root == nullptr)// preorder 函数被定义为返回 void 类型——不返回任何值// return; 仅仅是结束函数的执行,并不返回任何值return;// 存入向量的末尾res.push_back(root->val);// 前序——根左右preorder(root->left, res);preorder(root->right, res);}vector<int> preorderTraversal(TreeNode* root) {// 定义一个 矢量/向量——更准确地说是一个动态数组vector<int> res;preorder(root, res);return res;}
};
方法二 Morris遍历
/*** 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) {// 修改Ivector<int> res;if (root == nullptr)return res;TreeNode *cur = root;TreeNode *mostRight = nullptr;while (cur != nullptr) {mostRight = cur->left;// cur 有左树if (mostRight != nullptr) {// 最右节点不为空 且 不为curwhile (mostRight->right != nullptr && mostRight->right != cur){mostRight = mostRight->right;}// 第一次到达// cur左子树的 最右节点mostRight的右指针指向空// cur 向右移动if (mostRight->right == nullptr) {// 对于有左子树的节点——第一次收集// 修改II// emplace_back()也可res.push_back(cur->val);mostRight->right = cur;cur = cur->left;// 别忘了 continuecontinue;}// 第二次到达// cur左子树的 最右节点mostRight的右指针指向cur// cur 向左移动else {// 恢复mostRight->right = nullptr;// cur = cur->right;}} else {// 对于没有左子树的节点——直接收集// 修改IIIres.emplace_back(cur->val);}// cur 无子树,向右移动cur = cur->right;}// 修改IV// 别忘了 修改时在最后返回resreturn res;}
};
94.二叉树的中序遍历
🌟递归+迭代
原题链接
C++
若未特殊标明,以下题解均写用C++
方法一 递归 (DFS )
/*** 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:void inorder(TreeNode* root, vector<int>& res) {//可以另写成if (!root)if (!root) return;// 中序——左根右——先插入最左边的左孩子inorder(root->left, res);res.push_back(root->val);inorder(root->right, res);}vector<int> inorderTraversal(TreeNode* root) {vector<int> res;inorder(root, res);return res;}
};
方法二 Morris遍历
/*** 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) {// 修改Ivector<int> ans;if (root == nullptr)return ans;TreeNode *cur = root, *mostRight = nullptr;while (cur != nullptr) {mostRight = cur->left;if (mostRight != nullptr) {while (mostRight->right != nullptr && mostRight->right != cur)mostRight = mostRight->right;if (mostRight->right == nullptr) {mostRight->right = cur;cur = cur->left;continue;} else {// 修改IIans.push_back(cur->val);mostRight->right = nullptr;} } else {// 修改IIIans.push_back(cur->val);}cur = cur->right; }// 修改IVreturn ans;}
};
145.二叉树的后序遍历
🌟递归+迭代
原题链接
C++
若未特殊标明,以下题解均写用C++
方法一 递归 (DFS )
/*** 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:void postorder(TreeNode *root, vector<int> &res) {if (!root)return;// 后序——左右根postorder(root->left, res);postorder(root->right, res);// 左右都不存在才先插入根节点的值res.push_back(root->val);}vector<int> postorderTraversal(TreeNode* root) {vector<int> res;postorder(root, res);return res;}
};
方法二 迭代
/*** 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> res;// 空树if (!root) return res;// 定义一个 树节点栈stack<TreeNode* > stk;TreeNode *prev = nullptr;// 树没遍历完 或 栈非空while (root != nullptr || !stk.empty()) {// 树没遍历完while (root != nullptr) {// 遍历所有左节点 入栈// 将这个树节点 入栈stk.emplace(root);root = root->left;}// 若此时 root 为空// 更新 root root = stk.top();// 栈顶元素用完 弹出栈stk.pop();// 无右子节点 或 这个右子节点被遍历过if (root->right == nullptr || root->right == prev) {res.emplace_back(root->val);// 标记这个节点prev = root;root = nullptr;} // 有右子节点else { stk.emplace(root);root = root->right;}}return res;}
};
方法三 Morris遍历
class Solution {
public:void addPath(vector<int> &vec, TreeNode *node) {int count = 0;while (node != nullptr) {++count;vec.emplace_back(node->val);node = node->right;}reverse(vec.end() - count, vec.end());}vector<int> postorderTraversal(TreeNode *root) {vector<int> res;if (root == nullptr) {return res;}TreeNode *p1 = root, *p2 = nullptr;while (p1 != nullptr) {p2 = p1->left;if (p2 != nullptr) {while (p2->right != nullptr && p2->right != p1) {p2 = p2->right;}if (p2->right == nullptr) {p2->right = p1;p1 = p1->left;continue;} else {p2->right = nullptr;addPath(res, p1->left);}}p1 = p1->right;}addPath(res, root);return res;}
};
102.二叉树的层序遍历
🌟BFS+队列
原题链接
C++
若未特殊标明,以下题解均写用C++
方法一 BFS
/*** 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<vector<int>> levelOrder(TreeNode* root) {vector <vector <int>> ret;if (!root) {return ret;}queue <TreeNode*> q;q.push(root);while (!q.empty()) {int currentLevelSize = q.size();ret.push_back(vector <int> ());for (int i = 1; i <= currentLevelSize; ++i) {auto node = q.front(); q.pop();ret.back().push_back(node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right);}}return ret;}
};
方法二 队列
/*** 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) {}* };*/
// #include <queue>
// #include <vector>
class Solution {
public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> ans; if (root == nullptr )return ans; queue<TreeNode*> cur; cur.push(root); while (!cur.empty()) {// 当前层的节点数int size = cur.size();// 存储当前层的节点值 vector<int> vals; for (int i = 0; i < size; ++i) { TreeNode* node = cur.front(); cur.pop();vals.push_back(node->val);if (node->left)cur.push(node->left); if (node->right)cur.push(node->right); } ans.push_back(vals); // 将当前层的节点值添加到答案中 } return ans; }
};