1. 二叉树的前序、中序、后序遍历
（1）递归解决：根据前序遍历根左右，中序遍历左根右，后序遍历左右根即可。
class Solution {
public:vector<int> res;vector<int> preorderTraversal(TreeNode* root) {if(root==nullptr) return {};recur(root);return res;}void recur(TreeNode* root){if(root==nullptr) return;//1.前序遍历res.push_back(root->val);recur(root->left);recur(root->right);//2.后序遍历recur(root->left);res.push_back(root->val);recur(root->right);//3.后序遍历res.push_back(root->val);recur(root->right);recur(root->left);}
};
（2) 迭代实现
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> res;if(root==nullptr) return {};stack<TreeNode*> s;s.push(root);while(!s.empty()){TreeNode* cur=s.top();s.pop();if(cur!=nullptr){if(cur->right) s.push(cur->right);if(cur->left) s.push(cur->left);s.push(cur); // 前序：栈结构-“先进后出”，所以根最后进先出s.push(nullptr); //标记访问过//中序遍历if(cur->right) s.push(cur->right);s.push(cur); // 中序：栈结构-“先进后出”，push顺序为右根左s.push(nullptr); //标记访问过if(cur->left) s.push(cur->left);//后序遍历s.push(cur); // 后序：栈结构-“先进后出”，push顺序为根右左s.push(nullptr); //标记访问过if(cur->right) s.push(cur->right);if(cur->left) s.push(cur->left);}else{res.push_back(s.top()->val); //前面s.pop()已经去掉nullptr,//所以s.top()得到的是下面的值。s.pop();}}return res;}
};
2. 从前序和中序遍历序列构造二叉树、从中序和后序遍历序列构造二叉树
原理：
前序遍历：根-左-右
中序遍历：左-根-右
可以根据前序遍历得到根节点，然后在中序遍历中找到根节点的位置，可得左子树的节点数和右子树的节点数。递归即可。
代码
class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {return build(preorder,0,preorder.size()-1,inorder,0, inorder.size()-1);}TreeNode* build(vector<int>& preorder,int l1, int r1, vector<int>& inorder,int l2,int r2){//前+中-->构造二叉树if(l1>r1) return nullptr;TreeNode* root=new TreeNode(preorder[l1]);int k=l2;while(k<=r2 && inorder[k]!=root->val) k++;int left_len=k-l2;root->left =build(preorder,l1+1,l1+left_len, inorder,l2,k-1);root->right=build(preorder,l1+left_len+1,r1, inorder,k+1,r2);return root;//中+后-->构造二叉树if(l1>r1) return nullptr;TreeNode* root = new TreeNode(postorder[r2]);int k=l1;while(k<r1 && inorder[k]!= root->val) k++;int left_len=k-l1;root->left=build(inorder,l1,k-1,postorder,l2,l2+left_len-1);root->right=build(inorder,k+1,r1,postorder,l2+left_len,r2-1);return root;}
};
3. 二叉树的层序遍历
利用队列: push左，push右； 循环结束条件：q.empty（）
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;if(root==nullptr) return{};queue<TreeNode*> q;q.push(root);while(!q.empty()){vector<int> tmp;for(int i=q.size(); i>0; i--){TreeNode* cur=q.front();q.pop();tmp.push_back(cur->val);if(cur->left) q.push(cur->left);if(cur->right) q.push(cur->right);}res.push_back(tmp);}return res;}
};
4. 二叉树的“之”字形遍历
用deque: 头部出，尾部加； 设置flag：用来改变不同层内部的实现； 循环结束条件：dq.empty()；
class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> res;deque<TreeNode*> dq;if(root==nullptr) return res;dq.push_back(root);bool flag=true;while(!dq.empty()){vector<int> tmp;for(int i=dq.size();i>0;i--){//奇数层if(flag){TreeNode* node=dq.back();dq.pop_back();tmp.push_back(node->val);if(node->left!=nullptr) dq.push_front(node->left);if(node->right!=nullptr) dq.push_front(node->right);}//偶数层else{TreeNode* node=dq.front();dq.pop_front();tmp.push_back(node->val);if(node->right!=nullptr) dq.push_back(node->right);if(node->left!=nullptr) dq.push_back(node->left);}}res.push_back(tmp);flag=!flag;}return res;}
};
5. 二叉树的右视图
class Solution {
public:vector<int> rightSideView(TreeNode* root) {vector<int> res;queue<TreeNode*> q;if(root==nullptr) return res;q.push(root);while(!q.empty()){TreeNode* node;for(int k=q.size(); k>0; k--){node=q.front();q.pop();if(node->left!=nullptr) q.push(node->left);if(node->right!=nullptr) q.push(node->right);}res.push_back(node->val); //将每层的最右边的值push_back}return res;}
};