本文主要是介绍代码随想录训练营第十三天，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
第一题：
原题链接：144. 二叉树的前序遍历 - 力扣（LeetCode）
思路1：递归法
当传递下去的节点为空的时候，返回。
前序遍历的话顺序是根左右，因此一来变先将节点的值添加进res数组中，然后先向左递归再向右递归，结果都存在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> preorderTraversal(TreeNode* root) {vector<int> res;qianxu(root, res);return res;}
private:void qianxu(TreeNode* root, vector<int>& res){if(root == nullptr) return;res.push_back(root -> val);if(root -> left != nullptr) qianxu(root -> left, res);if(root -> right != nullptr) qianxu(root -> right, res);}
};思路2：
迭代法：
就是先定义一个栈，把二叉树的每一层的元素都放入栈中，然后对栈进行操作，把栈中的元素取出放入到结果数组中。注意要先将右节点放入栈中再将左节点放入栈中，因为出栈的时候是栈顶元素先出栈。
代码如下：
/*** 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) {stack<TreeNode*> st;vector<int> res;if(root == nullptr) return {};st.push(root);while(!st.empty()){TreeNode* node = st.top();st.pop();res.push_back(node -> val);if(node -> right != nullptr) st.push(node -> right);if(node -> left != nullptr) st.push(node -> left);}return res;}};中序遍历：
原题链接：94. 二叉树的中序遍历 - 力扣（LeetCode）
递归法：左根右。
代码如下：
/*** 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) {vector<int> res;zhongxu(root, res);return res;}
private:void zhongxu(TreeNode* root, vector<int>& res){if(root == nullptr) return;if(root -> left != nullptr) zhongxu(root -> left, res);res.push_back(root -> val);if(root -> right != nullptr) zhongxu(root -> right, 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> inorderTraversal(TreeNode* root) {stack<TreeNode*> st;if(root == nullptr) return {};vector<int> res;TreeNode* cur = root;while(cur != nullptr || !st.empty()){if(cur != nullptr){st.push(cur);cur = cur -> left; // 左}else{cur = st.top();st.pop();res.push_back(cur -> val); // 中cur = cur -> right; // 右}}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;houxu(root, res);return res;}
private:void houxu(TreeNode* root, vector<int>& res){if(root == nullptr) return;if(root -> left != nullptr) houxu(root -> left, res);if(root -> right != nullptr) houxu(root -> right, res);res.push_back(root -> val);}
};迭代法：
代码如下：
/*** 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;stack<TreeNode*> st;if(root == nullptr) return {};st.push(root);while(!st.empty()){TreeNode* node = st.top();st.pop();res.push_back(node -> val);if(node -> left) st.push(node -> left);if(node -> right) st.push(node -> right);}reverse(res.begin(), res.end());return res;}
};第二题：
原题链接：102. 二叉树的层序遍历 - 力扣（LeetCode）
思路：
用一个队列来保存每一层的元素，然后从队列前端弹出放入结果数组中即可。
注意的细节点：
在将每一层的元素放入数组中的时候，一定要将size提前声明并赋值好，不然在操作的时候que.size()是会变化的。
代码如下：
/*** 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>> res;if(root == nullptr) return {};queue<TreeNode*> que;que.push(root);while(!que.empty()){int size = que.size();vector<int> path;for(int i = 0; i < size; i++){TreeNode* node = que.front();path.push_back(node -> val);que.pop();if(node -> left) que.push(node -> left);if(node -> right) que.push(node -> right);}res.push_back(path);}return res;}
};这篇关于代码随想录训练营第十三天的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
