这里就用力扣上面的各种题目要模板了。

文章目录

二叉树的遍历层次遍历前序遍历、中序遍历、后序遍历的递归写法前序遍历、中序遍历、后序遍历的迭代写法Morris遍历 从中序遍历和前(后)序遍历构造二叉树从中序遍历和前(后)序遍历构造二叉树

二叉树的遍历

层次遍历

102. 二叉树的层序遍历

class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> ans; if(!root) return ans; queue<TreeNode*> q; q.push(root); while(!q.empty()){ int size = q.size(); vector<int> list; while(size--){ TreeNode* r = q.front(); q.pop(); list.push_back(r->val); if(r->left) q.push(r->left); if(r->right) q.push(r->right); } if(list.size()){ ans.push_back(list); } } return ans; } };

前序遍历、中序遍历、后序遍历的递归写法

144. 二叉树的前序遍历 94. 二叉树的中序遍历 145. 二叉树的后序遍历

// 先序 class Solution { public: vector<int> ans; vector<int> preorderTraversal(TreeNode* root) { preOrder(root); return ans; } void preOrder(TreeNode* root){ if(!root) return; ans.push_back(root->val); preOrder(root->left); preOrder(root->right); } }; // 中序 ```cpp class Solution { public: vector<int> ans; vector<int> inorderTraversal(TreeNode* root) { inOrder(root); return ans; } void inOrder(TreeNode* root){ if(!root) return; inOrder(root->left); ans.push_back(root->val); inOrder(root->right); } }; // 后序 class Solution { public: vector<int> ans; vector<int> postorderTraversal(TreeNode* root) { postorder(root); return ans; } void postorder(TreeNode* root){ if(!root) return; postorder(root->left); postorder(root->right); ans.push_back(root->val); } };

前序遍历、中序遍历、后序遍历的迭代写法

// 前序遍历最好写 class Solution { public: vector<int> ans; vector<int> preorderTraversal(TreeNode* root) { stack<TreeNode*> st; if(root) st.push(root); while(!st.empty()){ TreeNode* p = st.top(); st.pop(); ans.push_back(p->val); if(p->right) st.push(p->right); if(p->left) st.push(p->left); } return ans; } }; // 中序遍历 // 左 根 右，所以一直往左走，将经过的节点入栈，直到没有左孩子，然后输出现在的根，然后处理右子树。 class Solution { public: vector<int> ans; vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode*> st; while(root || st.size()){ while(root){ st.push(root); root = root->left; } root = st.top(); st.pop(); ans.push_back(root->val); root = root->right; } return ans; } }; // 更加直观的标记法 class Solution { public: vector<int> ans; typedef pair<TreeNode*,bool> P; vector<int> inorderTraversal(TreeNode* root) { stack<P> st; if(root) st.push({root,false}); while(!st.empty()){ P p = st.top(); st.pop(); if(p.second){ ans.push_back(p.first->val); }else{ p.second = true; if(p.first->right) st.push({p.first->right,false}); st.push(p); if(p.first->left) st.push({p.first->left,false}); } } return ans; } }; // 后序遍历 // 直观的标记法 class Solution { public: vector<int> ans; typedef pair<TreeNode*,bool> P; vector<int> postorderTraversal(TreeNode* root) { stack<P> st; st.push({root,false}); while(!st.empty()){ P p = st.top(); st.pop(); if(!p.first) continue; if(p.second){ ans.push_back(p.first->val); }else{ p.second = true; st.push(p); st.push({p.first->right,false}); st.push({p.first->left,false}); } } return ans; } }; // class Solution { public: vector<int> ans; vector<int> postorderTraversal(TreeNode* root) { stack<TreeNode*> st; if(root) st.push(root); TreeNode* pre = nullptr; while(!st.empty()){ while(st.top()->left || st.top()->right){ TreeNode* node = st.top(); // 如果左右子树已经访问过了,直接跳出,不要在入栈 if(node->right){ if(node->right == pre) break; st.push(node->right); } if(node->left){ if(node->left == pre) break; st.push(node->left); } } ans.push_back(st.top()->val); pre = st.top(); st.pop(); } return ans; } };

Morris遍历

挖个坑，以后填吧

从中序遍历和前(后)序遍历构造二叉树

注意：这种构造方法，首先必须要求有中序遍历（否则无法划分左右边界）。其次，必须保证个元素的唯一性，否则构造出的二叉树不唯一。

105. 从前序与中序遍历序列构造二叉树

class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int n = preorder.size(); return create(0,n-1,0,n-1,preorder,inorder); } TreeNode* create(int preL,int preR,int inL,int inR,vector<int>& preorder, vector<int>& inorder){ if(preL>preR){ return nullptr; } int val = preorder[preL]; TreeNode* node = new TreeNode(val); int idx = 0; for(int i=inL;i<=inR;i++){ if(inorder[i]==val){ idx = i; break; } } int numLeft = idx-inL; node->left = create(preL+1,preL+numLeft,inL,idx-1,preorder,inorder); node->right = create(preL+numLeft+1,preR,idx+1,inR,preorder,inorder); return node; } };

106. 从中序与后序遍历序列构造二叉树

class Solution { public: TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { int n = inorder.size(); return create(0,n-1,0,n-1,inorder,postorder); } TreeNode* create(int postL,int postR,int inL,int inR,vector<int>& inorder, vector<int>& postorder){ if(postL>postR){ return nullptr; } TreeNode* root = new TreeNode(postorder[postR]); int idx = 0; for(int i = inL;i<=inR;i++){ if(inorder[i]==postorder[postR]){ idx = i; break; } } int numLeft = idx-inL; root->left = create(postL,postL+numLeft-1,inL,idx-1,inorder,postorder); root->right = create(postL+numLeft,postR-1,idx+1,inR,inorder,postorder); return root; } };

先序遍历与后序遍历序列，求其中序遍历序列

题意： 给定一棵有n个结点的二叉树的先序遍历与后序遍历序列，求其中序遍历序列。 若某节点只有一个子结点，则此处将其看作左儿子结点 （题目来自牛客网）

做法也是一样的，找出根节点，然后根据规则，划分左右子树。

class Solution { private: struct Node{ int val; Node* left= nullptr,*right= nullptr; Node(int val):val(val){} }; Node* root; public: /** * 返回所求中序序列 * @param n int整型 二叉树节点数量 * @param pre int整型vector 前序序列 * @param suf int整型vector 后序序列 * @return int整型vector */ void inOrder(Node* p){ if(p== nullptr) return; inOrder(p->left); inOrderList.push_back(p->val); inOrder(p->right); } Node* create(vector<int>& pre,int pl,int pr, vector<int>& suf,int sl,int sr){ if(pl>pr) return nullptr; Node* p = new Node(pre[pl]); if(pl<pr){ int idx = -1; for(int i=sl;i<=sr;i++){ if(suf[i] == pre[pl+1]){ idx = i; break; } } int lenOfLeft = idx-sl+1; p->left = create(pre,pl+1,pl+lenOfLeft,suf,sl,sl+lenOfLeft-1); p->right = create(pre,pl+lenOfLeft+1,pr,suf,sl+lenOfLeft,sr-1); } return p; } vector<int> inOrderList; vector<int> solve(int n, vector<int>& pre, vector<int>& suf) { root = create(pre,0,n-1,suf,0,n-1); inOrder(root); return inOrderList; } };

从中序遍历和前(后)序遍历构造二叉树

暂时没找到相关题目。 大致思路是，根据层次遍历的有序性

别人的博客