网站应该怎么做运维,群晖 删除 wordpress,定制v下载安卓,建设网站企业邮箱网站建设服务仅做学习笔记#xff0c;详细请访问代码随想录
● 理论基础 ● 递归遍历 ● 迭代遍历 ● 统一迭代
单层递归的逻辑就是按照中左右的顺序来处理的#xff0c;这样二叉树的前序遍历#xff0c;基本就写完了#xff0c;再看一下完整代码#xff1a;
前序遍历#xff1a; …仅做学习笔记详细请访问代码随想录
● 理论基础 ● 递归遍历 ● 迭代遍历 ● 统一迭代
单层递归的逻辑就是按照中左右的顺序来处理的这样二叉树的前序遍历基本就写完了再看一下完整代码
前序遍历
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); // 中
}
● 迭代遍历 前序遍历迭代法
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;}
};中序遍历迭代法
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;}
};后序遍历迭代法
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;}
};
