南昌建站模板,有没有专门学做婴儿衣服的网站,郴州网站建设的公司,做普通网站多少钱系列目录
88.合并两个有序数组 52.螺旋数组 567.字符串的排列 643.子数组最大平均数 150.逆波兰表达式 61.旋转链表 160.相交链表 83.删除排序链表中的重复元素 389.找不同 1491.去掉最低工资和最高工资后的工资平均值 896.单调序列 206.反转链表 92.反转链表II 141.环形链表 …系列目录
88.合并两个有序数组 52.螺旋数组 567.字符串的排列 643.子数组最大平均数 150.逆波兰表达式 61.旋转链表 160.相交链表 83.删除排序链表中的重复元素 389.找不同 1491.去掉最低工资和最高工资后的工资平均值 896.单调序列 206.反转链表 92.反转链表II 141.环形链表 142.环型链表 21.合并两个有序列表 24.两辆交换链表中的节点 876.链表的中间节点 143. 重排链表 2.两数相加 445.两数相加II 目录 系列目录前言144.二叉树的前序遍历94.二叉树的中序遍历145.二叉树的后序遍历Morris遍历 102.二叉树的层序遍历 前言
方法都是类似的 递归是隐式调用栈(递归栈无需手动实现)迭代是显式调用栈 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, vectorint res) {if (root nullptr)// preorder 函数被定义为返回 void 类型——不返回任何值// return; 仅仅是结束函数的执行并不返回任何值return;// 存入向量的末尾res.push_back(root-val);// 前序——根左右preorder(root-left, res);preorder(root-right, res);}vectorint preorderTraversal(TreeNode* root) {// 定义一个 矢量/向量——更准确地说是一个动态数组vectorint res;preorder(root, res);return 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, vectorint res) {//可以另写成if (!root)if (!root) return;// 中序——左根右——先插入最左边的左孩子inorder(root-left, res);res.push_back(root-val);inorder(root-right, res);}vectorint inorderTraversal(TreeNode* root) {vectorint res;inorder(root, res);return res;}
};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, vectorint res) {if (!root)return;// 后序——左右根postorder(root-left, res);postorder(root-right, res);// 左右都不存在才先插入根节点的值res.push_back(root-val);}vectorint postorderTraversal(TreeNode* root) {vectorint 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:vectorint postorderTraversal(TreeNode* root) {vectorint res;// 空树if (!root) return res;// 定义一个 树节点栈stackTreeNode* 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(vectorint vec, TreeNode *node) {int count 0;while (node ! nullptr) {count;vec.emplace_back(node-val);node node-right;}reverse(vec.end() - count, vec.end());}vectorint postorderTraversal(TreeNode *root) {vectorint 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;}
};Morris遍历
Morris遍历是一种高效的二叉树遍历算法其显著特点是能在不使用栈或队列的情况下实现中序遍历且空间复杂度为O(1)
1. 基本思想 Morris遍历的基本思想是利用叶子节点的空指针来存储临时信息从而达到节省空间的目的 在遍历过程中Morris遍历会修改树中某些节点的指针指向以便在遍历时能够方便地回溯到上一个节点 遍历完成后需要还原树的结构
2. 实现过程 Morris遍历的实现过程可以分为以下几个步骤
对于当前遍历到的节点如果它有左子节点就找到左子树中最右边的节点 (记为mostRight )将其右子节点指向当前节点将当前节点更新为其左子节点继续遍历如果当前节点没有左子节点就输出当前节点的值 (或进行其他操作)并将当前节点更新为其右子节点重复以上步骤直到遍历完整棵树
3. 遍历类型 Morris遍历可以实现前序、中序和后序遍历 具体实现时需要根据遍历的顺序调整指针的指向和节点的访问顺序
前序遍历在第一次访问节点时输出节点的值然后进行左子树的遍历中序遍历在第二次访问节点时(即mostRight的右指针指向当前节点时)输出节点的值然后进行右子树的遍历后序遍历后序遍历的实现相对复杂需要在遍历过程中记录左子树最右分支的路径并在回溯时逆序输出
4. 优缺点
优点Morris遍历的空间复杂度为O(1)比使用栈或递归的遍历算法更高效 此外Morris遍历不会占用额外的内存空间对于内存受限的环境非常友好缺点Morris遍历会修改原始树的结构需要在遍历完成后还原 此外Morris遍历的实现相对复杂需要理解其背后的思想和原理
5. 应用场景 Morris遍历适用于需要高效遍历二叉树且内存受限的场景 例如在处理大规模数据时使用Morris遍历可以节省内存空间并提高遍历效率 同时Morris遍历也可以用于实现一些特殊的算法和数据结构如线索二叉树等 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:vectorvectorint 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: vectorvectorint levelOrder(TreeNode* root) { vectorvectorint ans; if (root nullptr )return ans; queueTreeNode* cur; cur.push(root); while (!cur.empty()) {// 当前层的节点数int size cur.size();// 存储当前层的节点值 vectorint 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; }
};
