做网站的是什么工程师,搜索引擎的工作原理是什么,怎样登录韵网网站,永久免费云服务器无需注册前中后序遍历#xff08;DFS#xff09;
首先我们要明确前中后序遍历的顺序#xff1a;
前序#xff1a;中左右中序#xff1a;左中右后序#xff1a;左右中
前中后序遍历的递归代码和迭代代码分别有各自的框架#xff0c;然后根据遍历顺序调整记录元素的位置即可。 …前中后序遍历DFS
首先我们要明确前中后序遍历的顺序
前序中左右中序左中右后序左右中
前中后序遍历的递归代码和迭代代码分别有各自的框架然后根据遍历顺序调整记录元素的位置即可。
递归
class Solution {
private:void postOrder(TreeNode* root, vectorint vec) {if (!root) return;postOrder(root-left, vec); // 1postOrder(root-right, vec);// 2vec.push_back(root-val); // 3}
public:vectorint postorderTraversal(TreeNode* root) {vectorint res;postOrder(root, res);return res;}
};前序遍历3-1-2中序遍历1-3-2后序遍历1-2-3
如前所述三种遍历的迭代方式很简单并且更改迭代方式只要调整记录元素的位置即可。
迭代
前序遍历
我们以前序遍历给出迭代版本的框架核心思想就是用栈。
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {vectorint res;stackTreeNode* S;TreeNode* node root;while (node || !S.empty()) {while (node) {res.push_back(node-val); // 注意S.push(node);node node-left;}node S.top(); S.pop();node node-right; }return res;}
};中序遍历
与前序遍历的差别请看代码中的 注意调整了记录元素的位置。
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {if (!root) return {};vectorint res;stackTreeNode* S;TreeNode* curr root;while (curr || !S.empty()) {while (curr) {S.push(curr);curr curr-left;}TreeNode* node S.top();S.pop();res.push_back(node-val); // 注意curr node-right;}return res;}
};后序遍历
注意到前序遍历的顺序为中左右而我们想要的后序遍历的顺序为左右中。我们可以先讲前序遍历代码中访问左右子树的顺序互换得到顺序为中右左再进行 reverse得到后序左右中。
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {if (!root) return {};vectorint res;stackTreeNode* S;S.push(root);while (!S.empty()) {TreeNode* node S.top();S.pop();res.push_back(node-val);if (node-left) S.push(node-left);if (node-right) S.push(node-right);}reverse(res.begin(), res.end());return res;}
};层序遍历BFS
不需按深度划分
直接输出层序遍历序列不需按深度划分不同于 DFS 使用栈这里是用队。
class Solution {
public:vectorint levelOrder(TreeNode* root) {if (!root) return {};queueTreeNode* Q;// vectorvectorint res;vectorint res;Q.push(root);while (!Q.empty()) {TreeNode* curr Q.front();res.push_back(curr-val);Q.pop();if(curr-left) Q.push(curr-left);if(curr-right) Q.push(curr-right);}return res;}
}需要按深度划分
注意在不需要按深度划分的版本的基础上做些改变用 n 记录当前深度的节点的个数然后在 for 循环中将这 n 个节点保存到一个数组中下一层深度再用一个新数组保存从而达到按深度划分。
注意在本题的基础上修改可解决 LeetCode 中许多层序遍历的变种问题。
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {if (!root) return {};vectorvectorint res;queueTreeNode* Q;Q.push(root);while (!Q.empty()) {vectorint vec;int n Q.size();for (int i0; in; i) {TreeNode* curr Q.front();Q.pop();vec.push_back(curr-val);if (curr-left) Q.push(curr-left);if (curr-right) Q.push(curr-right);}res.push_back(vec);}return res;}
}Ref
https://github.com/youngyangyang04/leetcode-master/blob/master/problems/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.md
