前言
本篇总结了常见二叉树算法题,每个标题都有超链接,并给出AC代码。记得以后再刷几遍,容易忘记。
1. 根据二叉树创建字符串
/** * 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: string tree2str(TreeNode* root) { if(root==nullptr) return string(); string str; str+=to_string(root->val); //左边不为空或者左边为空右边不为空,左边需要加括号 if(root->left||root->right) { str+='('; str+=tree2str(root->left); str+=')'; } //右边不为空,右边需要加括号 if(root->right) { str+='('; str+=tree2str(root->right); str+=')'; } return str; } };
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<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*>q; size_t levelSize = 0; if(root) { q.push(root); levelSize=1; } vector<vector<int>> vv; while(!q.empty()) { //控制一层一层出 vector<int> v; for(size_t i=0;i<levelSize;++i) { TreeNode* front = q.front(); q.pop(); v.push_back(front->val); if(front->left) q.push(front->left); if(front->right) q.push(front->right); } vv.push_back(v); //当前层出完了,下一层都进队列,队列的size就是下一层的数据个数 levelSize=q.size(); } return vv; } };
3. 二叉树的层序遍历 II
/** * 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>> levelOrderBottom(TreeNode* root) { queue<TreeNode*>q; size_t levelSize = 0; if(root) { q.push(root); levelSize=1; } vector<vector<int>> vv; while(!q.empty()) { //控制一层一层出 vector<int> v; for(size_t i=0;i<levelSize;++i) { TreeNode* front = q.front(); q.pop(); v.push_back(front->val); if(front->left) q.push(front->left); if(front->right) q.push(front->right); } vv.push_back(v); //当前层出完了,下一层都进队列,队列的size就是下一层的数据个数 levelSize=q.size(); } reverse(vv.begin(),vv.end()); return vv; } };
4. 二叉树的最近公共祖先
方法一:O(H*N)
1./** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool Find(TreeNode* sub,TreeNode* x) { if(sub==nullptr) return false; return sub == x ||Find(sub->left,x) ||Find(sub->right,x); } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root==nullptr) return nullptr; if(root == p || root == q) return root; bool pInLeft,pInRight,qInLeft,qInRight; pInLeft = Find(root->left,p); pInRight = !pInLeft; qInLeft = Find(root->left,q); qInRight = !qInLeft; //1、一个在左一个在右,root就是最近公共祖先 //2、都在左,递归去左子树找 //3、都在右,递归去右子树找 if((pInLeft&&qInRight)||(qInLeft&&pInRight)) { return root; } else if(pInLeft&&qInLeft) { return lowestCommonAncestor(root->left,p,q); } else if(pInRight&&qInRight) { return lowestCommonAncestor(root->right,p,q); } else { //理论上不会走到这里 return nullptr; } } };
方法二:O(N)
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool FindPath(TreeNode* root,TreeNode* x,stack<TreeNode*>&path) { if(root==nullptr) return false; path.push(root); if(root == x) return true; if(FindPath(root->left,x,path)) return true; if(FindPath(root->right,x,path)) return true; path.pop(); return false; } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { stack<TreeNode*>pPath,qPath; FindPath(root,p,pPath); FindPath(root,q,qPath); //类似链表相交 while(pPath.size()!=qPath.size()) { if(pPath.size()>qPath.size()) pPath.pop(); else qPath.pop(); } while(pPath.top()!=qPath.top()) { pPath.pop(); qPath.pop(); } return pPath.top(); } };
5.二叉搜索树与双向链表
1./* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: void InOrderConvert(TreeNode* cur,TreeNode*& prev) { if(cur == nullptr) return; InOrderConvert(cur->left, prev); cur->left = prev; if(prev) prev->right=cur; prev = cur; InOrderConvert(cur->right, prev); } TreeNode* Convert(TreeNode* pRootOfTree) { TreeNode* prev = nullptr; InOrderConvert(pRootOfTree,prev); TreeNode* head = pRootOfTree; while(head&&head->left) { head=head->left; } return head; } };
6.从前序与中序遍历序列构造二叉树
/** * 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: TreeNode* _buildTree(vector<int>&preorder,vector<int>&inorder,int& prei,int inbegin, int inend) { if(inbegin>inend) return nullptr; TreeNode* root = new TreeNode(preorder[prei++]); //分割中序 int ini=inbegin; while(ini <= inend) { if(inorder[ini] == root->val) break; else ++ini; } //[inbegin,ini-1] ini [ini+1,inend] root->left = _buildTree(preorder,inorder,prei,inbegin,ini-1); root->right = _buildTree(preorder,inorder,prei,ini+1,inend); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { int i=0; return _buildTree(preorder,inorder,i,0,inorder.size()-1); } };
7. 二叉树的前序遍历非递归
/** * 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> result; stack<TreeNode*> st; if(root==nullptr)return result; st.push(root); TreeNode* cur=nullptr; while(!st.empty()) { cur=st.top(); st.pop(); result.push_back(cur->val); if(cur->right)st.push(cur->right); if(cur->left)st.push(cur->left); } return result; } }; //法二 class Solution { public: vector<int> preorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> v; TreeNode* cur = root; while(cur || !st.empty()) { //开始访问一棵树 //1、左路节点 while(cur) { v.push_back(cur->val); st.push(cur); cur = cur->left; } // 2、左路节点的右子树需要访问 TreeNode*top = st.top(); st.pop(); cur = top->right; } return v; } };
8. 二叉树的中序遍历非递归
/** * 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> result; stack<TreeNode*> st; TreeNode*cur=root; while(cur!=nullptr||!st.empty()) { if(cur!=nullptr) { st.push(cur); cur=cur->left; } else { cur=st.top(); result.push_back(cur->val); st.pop(); cur=cur->right; } } return result; } }; //法二 class Solution { public: vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> v; TreeNode* cur = root; while(cur || !st.empty()) { //开始访问一棵树 //1、左路节点入栈 while(cur) { st.push(cur); cur = cur->left; } // 2、当左路节点从栈中出来,表示左子树已经访问过了,应该访问这个节点和它的右节点 TreeNode*top = st.top(); st.pop(); v.push_back(top->val); cur = top->right; } return v; } };
9. 二叉树的后序遍历非递归
/** * 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> result; stack<TreeNode*> st; if(root==NULL)return result; TreeNode*cur=NULL; TreeNode*pre=NULL; st.push(root); while(!st.empty()) { cur=st.top(); if((cur->left==NULL&&cur->right==NULL)|| (pre!=NULL&&(pre==cur->left||pre==cur->right))) { result.push_back(cur->val); st.pop(); pre=cur; } else { if(cur->right!=NULL)st.push(cur->right); if(cur->left!=NULL)st.push(cur->left); } } return result; } }; //法二 class Solution { public: vector<int> postorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> v; TreeNode* cur = root; TreeNode* prev = nullptr; while(cur || !st.empty()) { //开始访问一棵树 //1、左路节点入栈 while(cur) { st.push(cur); cur = cur->left; } // 2、当左路节点从栈中出来,表示左子树已经访问过了 TreeNode*top = st.top(); //栈顶节点右子树为空或者上一个访问节点是右子树的根,说明右子树已经访问过了,可以访问上一个节点的右数 //否则 子问题访问top的右子树 if(top->right == nullptr||top->right == prev) { v.push_back(top->val); prev = top; cur = nullptr; st.pop(); } else{ cur = top->right;//子问题访问右子树 } } return v; } };