二叉树day1

二叉树的递归遍历

144 二叉树的前序遍历

vector的push_back方法res.push_back(root->val);
vector的insert方法res.insert(res.end(),right_res.begin(),right_res.end());
在res的vector res.end()位置之前插入[right_res.begin(),right_res.end())之间的内容。

// struct TreeNode{
//     int val;
//     TreeNode* left;
//     TreeNode* right;
//     TreeNode(int x,TreeNode* left=nullptr,TreeNode*right=nullptr):val(x),left(left),right(right){}
// };
class Solution{
public:vector<int> preorderTraversal(TreeNode* root){vector<int> res;if(root==nullptr) return res;res.push_back(root->val);//push_back将元素添加到vector数组末尾//begin指向vector的第一个元素，end指向vecotr的最后一个元素的下一个位置//递归左子树，并将结果整合到res中vector<int> left_res = preorderTraversal(root->left);res.insert(res.end(),left_res.begin(),left_res.end());//递归右子树，并将结果整合到res中vector<int> right_res = preorderTraversal(root->right);res.insert(res.end(),right_res.begin(),right_res.end());  //范围插入法// 3. 在 pos 位置插入 [first, last) 范围内的元素（范围插入）// template< class InputIt >// iterator insert(iterator pos, InputIt first, InputIt last);//也就是在pos位置前一个，插入[first,last)的所有元素return res;}
};

145二叉树的中序遍历

/*** 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 traversal(TreeNode* cur,vector<int>& vec){ //引用动态数组if(cur==nullptr) return;traversal(cur->left,vec);traversal(cur->right,vec);vec.push_back(cur->val);}vector<int> postorderTraversal(TreeNode* root){vector<int> res;traversal(root,res);return res;}
};

94 二叉树的中序遍历

/*** 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 traversal(TreeNode* cur,vector<int>& res){if (cur==nullptr) return;traversal(cur->left,res);res.push_back(cur->val);traversal(cur->right,res);}vector<int> inorderTraversal(TreeNode* root){vector<int> res;traversal(root,res);return res;}
};

二叉树的迭代遍历

144 二叉树的前序遍历（迭代版）

使用了栈的想法，将二叉树结点按照中右左的顺序压入进去，然后弹出的时候，如果有右左结点，则弹出后将右左结点再压入进去。

/*** 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;// st栈中存的全是TreeNode指针变量vector<int> result;if(root==nullptr)return result;st.push(root);//先把root压入栈中while(!st.empty()){//若st不为空，则说明没有子结点压进去了TreeNode* node = st.top();//栈顶元素赋值nodest.pop();//弹出result.push_back(node->val); //也就是给结果矩阵中压入结果if(node->right) st.push(node->right);if(node->left) st.push(node->left);}return result;}
};

145 二叉树的后序遍历

后序遍历“左右中”
前序遍历“中左右”
因此只需要交换一下遍历顺序即可，前序遍历的中左右，交换顺序中右左然后再倒过来左右中

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> 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;}
};

94 二叉树的中序遍历

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> 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:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;//创建一个队列帮助层序遍历if(root!=nullptr) que.push(root);//把root先放进队列中vector<vector<int>> result; //result是一个动态数组，动态数组元素为vector<int>，存储的是每一层的遍历结果while(!que.empty()){//当que不为空时int size = que.size(); //que.size()存储的是当前层有多少个结点vector<int> vec; // 存储当前层的结点值for (int i=0;i<size;i++){TreeNode* node = que.front();//取出队列前面的元素que.pop();vec.push_back(node->val);if(node->left) que.push(node->left);if(node->right) que.push(node->right);}result.push_back(vec);}return result;}
};