成都市建设网站首页,用vue做pc端网站好吗,韩国建设部网站,长长沙网站制作目录
递归遍历
前序遍历
迭代遍历
前序遍历#xff08;迭代法#xff09;
中序遍历#xff08;迭代法#xff09;
后序遍历#xff08;迭代法#xff09;
统一迭代法
统一迭代 嵌入式学习分享个人主页#xff1a;Orion嵌入式随想录 - 小红书 (xiaohongshu.com) …目录
递归遍历
前序遍历
迭代遍历
前序遍历迭代法
中序遍历迭代法
后序遍历迭代法
统一迭代法
统一迭代 嵌入式学习分享个人主页Orion嵌入式随想录 - 小红书 (xiaohongshu.com)
递归遍历 144.二叉树的前序遍历(opens new window) 94.二叉树的中序遍历 145.二叉树的后序遍历(opens new window) 文章讲解代码随想录
前序遍历 确定递归函数的参数和返回值 确定哪些参数是递归的过程中需要处理的那么就在递归函数里加上这个参数 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。 确定终止条件 写完了递归算法, 运行的时候经常会遇到栈溢出的错误就是没写终止条件或者终止条件写的不对操作系统也是用一个栈的结构来保存每一层递归的信息如果递归没有终止操作系统的内存栈必然就会溢出。 确定单层递归的逻辑 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。 解题思路 确定递归函数的参数和返回值因为要打印出前序遍历节点的数值所以参数里需要传入vector来放节点的数值除了这一点就不需要再处理什么数据了也不需要有返回值所以递归函数返回类型就是void代码如下 void traversal(TreeNode* cur, vectorint vec) 确定终止条件在递归的过程中如何算是递归结束了呢当然是当前遍历的节点是空了那么本层递归就要结束了所以如果当前遍历的这个节点是空就直接return代码如下 if (cur NULL) return; 确定单层递归的逻辑前序遍历是中左右的循序所以在单层递归的逻辑是要先取中节点的数值代码如下 vec.push_back(cur-val); // 中 traversal(cur-left, vec); // 左 traversal(cur-right, vec); // 右 代码注意 if (cur NULL) return;终止条件 cur-val当前指针 cur 所指向的对象的 val 成员变量的值 代码一前序遍历
class Solution {
public:void traversal(TreeNode* cur, vectorint vec) {if (cur NULL) return;vec.push_back(cur-val); // 中traversal(cur-left, vec); // 左traversal(cur-right, vec); // 右}vectorint preorderTraversal(TreeNode* root) {vectorint result;traversal(root, result);return result;}
}; 代码二中序遍历
void traversal(TreeNode* cur, vectorint vec) {if (cur NULL) return;traversal(cur-left, vec); // 左vec.push_back(cur-val); // 中traversal(cur-right, vec); // 右
} 代码三后序遍历
void traversal(TreeNode* cur, vectorint vec) {if (cur NULL) return;traversal(cur-left, vec); // 左traversal(cur-right, vec); // 右vec.push_back(cur-val); // 中
}
迭代遍历 文章讲解programmercarl.com
前序遍历迭代法 为什么可以用迭代法非递归的方式来实现二叉树的前后中序遍历呢在栈与队列匹配问题都是栈的强项 (opens new window)中提到了递归的实现就是每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中然后递归返回的时候从栈顶弹出上一次递归的各项参数所以这就是递归为什么可以返回上一层位置的原因。 解题思路 前序遍历是中左右每次先处理的是中间节点那么先将根节点放入栈中然后将右孩子加入栈再加入左孩子。 解题步骤 定义栈存放节点 定义数组存放结构 确定终止条件根节点入栈 循环处理栈栈不为空则获取栈并弹出获取不为空则按中左右顺序将值加入数组 代码一前序遍历迭代法
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint result;if (root NULL) return result;st.push(root);while (!st.empty()) {TreeNode* node st.top(); // 中st.pop();result.push_back(node-val);if (node-right) st.push(node-right); // 右空节点不入栈if (node-left) st.push(node-left); // 左空节点不入栈}return result;}
};
中序遍历迭代法 在迭代的过程中有两个操作 处理将元素放进result数组中 访问遍历节点 解题思路 前序遍历的顺序是中左右先访问的元素是中间节点要处理的元素也是中间节点所以刚刚才能写出相对简洁的代码因为要访问的元素和要处理的元素顺序是一致的都是中间节点。 中序遍历是左中右先访问的是二叉树顶部的节点然后一层一层向下访问直到到达树左面的最底部再开始处理节点也就是在把节点的数值放进result数组中这就造成了处理顺序和访问顺序是不一致的。 在使用迭代法写中序遍历就需要借用指针的遍历来帮助访问节点栈则用来处理节点上的元素。 解题步骤 定义栈存放节点 定义数组存放结构 定义指针用于遍历 循环处理栈指针、栈不为空则存入栈并向左走为空则弹出处理存入数组再向右走 代码二中序遍历迭代法
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint result;stackTreeNode* st;TreeNode* cur root;while (cur ! NULL || !st.empty()) {if (cur ! NULL) { // 指针来访问节点访问到最底层st.push(cur); // 将访问的节点放进栈cur cur-left; // 左} else {cur st.top(); // 从栈里弹出的数据就是要处理的数据放进result数组里的数据st.pop();result.push_back(cur-val); // 中cur cur-right; // 右}}return result;}
};
后序遍历迭代法 解题思路 先序遍历是中左右后续遍历是左右中只需要调整一下先序遍历的代码顺序就变成中右左的遍历顺序然后在反转result数组输出的结果顺序就是左右中。 解题步骤 定义栈存放节点 定义数组存放结构 确定终止条件根节点入栈 循环处理栈栈不为空则获取栈并弹出获取不为空则按中右左顺序将值加入数组 反转数组为左右中顺序 代码三后序遍历迭代法
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint result;if (root NULL) return result;st.push(root);while (!st.empty()) {TreeNode* node st.top();st.pop();result.push_back(node-val);if (node-left) st.push(node-left); // 相对于前序遍历这更改一下入栈顺序 空节点不入栈if (node-right) st.push(node-right); // 空节点不入栈}reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了return result;}
};统一迭代法 文章讲解代码随想录
统一迭代 迭代法实现的先中后序其实风格也不是那么统一除了先序和后序有关联中序完全就是另一个风格了一会用栈遍历一会又用指针来遍历。 针对三种遍历方式使用迭代法是可以写出统一风格的代码将访问的节点放入栈中把要处理的节点也放入栈中但是要做标记。如何标记呢就是要处理的节点放入栈之后紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。 解题思路 将访问的节点直接加入到栈中但如果是处理的节点则后面放入一个空节点 这样只有空节点弹出的时候才将下一个节点放进结果集。 代码一中序遍历
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint result;stackTreeNode* st;if (root ! NULL) st.push(root);while (!st.empty()) {TreeNode* node st.top();if (node ! NULL) {st.pop(); // 将该节点弹出避免重复操作下面再将右中左节点添加到栈中if (node-right) st.push(node-right); // 添加右节点空节点不入栈st.push(node); // 添加中节点st.push(NULL); // 中节点访问过但是还没有处理加入空节点做为标记。if (node-left) st.push(node-left); // 添加左节点空节点不入栈} else { // 只有遇到空节点的时候才将下一个节点放进结果集st.pop(); // 将空节点弹出node st.top(); // 重新取出栈中元素st.pop();result.push_back(node-val); // 加入到结果集}}return result;}
}; 代码二前序遍历
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint result;stackTreeNode* st;if (root ! NULL) st.push(root);while (!st.empty()) {TreeNode* node st.top();if (node ! NULL) {st.pop();if (node-right) st.push(node-right); // 右if (node-left) st.push(node-left); // 左st.push(node); // 中st.push(NULL);} else {st.pop();node st.top();st.pop();result.push_back(node-val);}}return result;}
}; 代码三后序遍历
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {vectorint result;stackTreeNode* st;if (root ! NULL) st.push(root);while (!st.empty()) {TreeNode* node st.top();if (node ! NULL) {st.pop();st.push(node); // 中st.push(NULL);if (node-right) st.push(node-right); // 右if (node-left) st.push(node-left); // 左} else {st.pop();node st.top();st.pop();result.push_back(node-val);}}return result;}
};
说明基于代码随想录课程学习部分内容引用代码随想录文章
