商務(wù)網(wǎng)站建設(shè)數(shù)據(jù)處理100個(gè)免費(fèi)推廣b站
目錄
1.二叉搜索樹(shù)的最近公共祖先
?2.在二叉樹(shù)中找到兩個(gè)節(jié)點(diǎn)的最近公共祖先
3.序列化二叉樹(shù)
4.重建二叉樹(shù)
?5.輸出二叉樹(shù)的右視圖
6.組隊(duì)競(jìng)賽
?7.刪除公共字符?
?
1.二叉搜索樹(shù)的最近公共祖先
這是一個(gè)簡(jiǎn)單的問(wèn)題,因?yàn)槭嵌嫠阉鳂?shù)(有序),首先看看p,q是不是都在左子樹(shù)?右子樹(shù)
如果不是,那么現(xiàn)在的根就是兩個(gè)的最近公共祖先
int lowestCommonAncestor(TreeNode* root, int p, int q) {// write code here、if(!root) return -1;if(p<root->val &&q<root->val) return lowestCommonAncestor(root->left, p, q);else if(p>root->val && q>root->val) return lowestCommonAncestor(root->right, p, q);//在兩個(gè)子樹(shù)else return root->val;}
?2.在二叉樹(shù)中找到兩個(gè)節(jié)點(diǎn)的最近公共祖先
最一般的樹(shù)怎么找最近公共祖先?
?最直觀的方法肯定是和上面搜索樹(shù)的想法一樣,先看看這兩個(gè)節(jié)點(diǎn)是不是在一側(cè)的子樹(shù)里
但是這不是搜索樹(shù),不可以比較節(jié)點(diǎn)的值來(lái)判斷在左子樹(shù)/右子樹(shù)
沒(méi)有條件創(chuàng)造條件也要上,誰(shuí)讓我想不出來(lái)更好的思路....
bool Isintree(TreeNode* root, int x) {if (!root) return false;return root->val == x||Isintree(root->left, x) ||Isintree(root->right, x);}int lowestCommonAncestor(TreeNode* root, int o1, int o2) {if (!root) return -1;if (root->val == o1 || root->val == o2) return root->val;bool Iso1inleft = Isintree(root->left, o1);bool Iso1inright = !Iso1inleft;bool Iso2inleft = Isintree(root->left, o2);bool Iso2inright = !Iso2inleft;if ((Iso1inleft && Iso2inright) || (Iso1inright && Iso2inleft))return root->val;if (Iso1inleft && Iso2inleft)return lowestCommonAncestor(root->left, o1, o2);elsereturn lowestCommonAncestor(root->right, o1, o2);}
?欣喜若狂的提交,超時(shí)!!!!!!!!!!!!!!!!!!!!!!!!!!!!
為什么?
因?yàn)樵谧訕?shù)里搜索很浪費(fèi)時(shí)間
?那么只能換方法
記得我們?cè)趺醋鱿嘟绘湵淼念}目嗎?
想找到鏈表的交點(diǎn),那么我們計(jì)算兩個(gè)鏈表的長(zhǎng)度,讓更長(zhǎng)的鏈表先走差距(兩個(gè)鏈表長(zhǎng)度差)步,然后挨個(gè)比較目前的val值,找到一樣的就輸出
那你看這個(gè)樹(shù)枝是不是很像鏈表
所以思路就有了
bool FindPath(TreeNode* root, stack<int>& s, int o) //找到這個(gè)節(jié)點(diǎn)的所有祖先
{if (!root) return false; //遇到空節(jié)點(diǎn)肯定不是祖先s.push(root->val); //先把這個(gè)節(jié)點(diǎn)入棧if (root->val == o) //找到了目標(biāo)節(jié)點(diǎn),直接返回return true;if (FindPath(root->left, s, o)) return true; //在左子樹(shù)里找到他,返回trueif (FindPath(root->right, s, o)) return true; //右子樹(shù)中找到他,trues.pop(); //走到這說(shuō)明左/右子樹(shù)沒(méi)找到這個(gè)節(jié)點(diǎn) ,這個(gè)root就不是目標(biāo)節(jié)點(diǎn)的祖先,popreturn false; //返回在這個(gè)路徑?jīng)]找到
}
int lowestCommonAncestor(TreeNode* root, int o1, int o2) {// 兩個(gè)棧記錄他們的祖先列表stack<int> s1;stack<int> s2;FindPath(root, s1, o1);FindPath(root, s2, o2);while (s1.size() < s2.size()) //長(zhǎng)度不一樣s2.pop(); //更長(zhǎng)的popwhile (s1.size() > s2.size())s1.pop();while (s1.top() != s2.top()) //當(dāng)前不是公共祖先 {//都把這個(gè)節(jié)點(diǎn)pops1.pop();s2.pop();}return s1.top(); //或者s2.top() 都一樣的值
}
3.序列化二叉樹(shù)
寫兩個(gè)函數(shù),讓字符串可以構(gòu)建成二叉樹(shù),二叉樹(shù)也可以寫成字符串
void dfs_Serialize(TreeNode* root, string& s)
{if (!root)//如果是空節(jié)點(diǎn),直接寫一個(gè)#,空節(jié)點(diǎn)的子節(jié)點(diǎn)被省略,所以直接返回{s += '#';return;}s += to_string(root->val) + ','; //把非空節(jié)點(diǎn)的val變成字符,寫入到字符串dfs_Serialize(root->left, s); //左子樹(shù)dfs_Serialize(root->right, s);//右子樹(shù)
}
char* Serialize(TreeNode* root) { //用二叉樹(shù)寫字符串?dāng)?shù)組string s; //首先寫成字符串dfs_Serialize(root, s); //深度優(yōu)先遍歷(前序)char* ans = new char[s.size() + 1]; //最后應(yīng)該輸出數(shù)組形式,先開(kāi)數(shù)組(加上1寫'\0')memcpy(ans, s.c_str(), s.size()); //把字符串拷貝給數(shù)組ans[s.size()] = '\0';//終止符return ans;
}
TreeNode* dfs_Deserialize(char*& s) //把字符串變二叉樹(shù),注意這個(gè)字符串在遞歸的時(shí)候不是每次從頭開(kāi)始,所以&
{if (*s == '#')//是空節(jié)點(diǎn)的標(biāo)志,直接返回nullptr{s++; //s向后走一個(gè),因?yàn)檫@個(gè)字符對(duì)應(yīng)的節(jié)點(diǎn)已經(jīng)被表示完了return nullptr;}int val = 0; //字符串對(duì)應(yīng)的節(jié)點(diǎn)valwhile (*s != ',') //看樣例,字符串以,分割{val = val * 10 + (*s - '0'); //萬(wàn)一不是個(gè)位數(shù),需要這樣算好每一位s++;//s往后走}s++; //把逗號(hào)跳過(guò)TreeNode* root = new TreeNode(val); //用val創(chuàng)建節(jié)點(diǎn)root->left = dfs_Deserialize(s); //左節(jié)點(diǎn)的創(chuàng)建root->right = dfs_Deserialize(s);//右節(jié)點(diǎn)return root; //返回根
}
TreeNode* Deserialize(char* str) {return dfs_Deserialize(str);
}
還有第二個(gè)方法,借助隊(duì)列,把字符串構(gòu)建成二叉樹(shù)(這個(gè)顯然沒(méi)有上面的方法快)
char* Serialize(TreeNode* root) { //用層序來(lái)寫字符串if (!root) return nullptr; //如果是空節(jié)點(diǎn),不需要記錄他的孩子string str; queue<TreeNode*> que;que.push(root); //先把根入隊(duì)while (!que.empty()){auto node = que.front(); //取隊(duì)頭元素que.pop();if (node) //取出的節(jié)點(diǎn)不是空{(diào)str += to_string(node->val) + ","; //字符串保存這個(gè)節(jié)點(diǎn)val對(duì)應(yīng)的字符,并且在字符串里面寫入分割符號(hào)que.push(node->left);//帶入左孩子que.push(node->right);}else {str += "#";//是空,寫成#}}auto res = new char[str.size() + 1]; //和上一方法這里的用處一樣strcpy(res, str.c_str());res[str.size()] = '\0';return res;
}
int Getinteger(char* str, int& k) //把字符轉(zhuǎn)化成數(shù)字
{int val = 0;while (str[k] != ',' && str[k] != '\0' && str[k] != '#'){val = val * 10 + str[k] - '0';++k;}if (str[k] == '\0') return -1;if (str[k] == '#') val = -1;k++;return val;
}
TreeNode* Deserialize(char* str) {if (!str) return nullptr;int k = 0; //記錄字符串的下標(biāo)queue<TreeNode* > que;auto head = new TreeNode(Getinteger(str, k)); //一定要把字符串下標(biāo)也傳,要不然找不到位置了que.push(head); //把頭結(jié)點(diǎn)入隊(duì)while (!que.empty()){auto node = que.front();//隊(duì)頭que.pop();//這里的反序列化是根據(jù)前序用字符串構(gòu)建二叉樹(shù)int leftval = Getinteger(str, k); //把字符串轉(zhuǎn)換成左節(jié)點(diǎn)的valif (leftval != -1)//如果左孩子的val是-1,代表是空節(jié)點(diǎn){//不是空auto nodeleft = new TreeNode(leftval) ;//創(chuàng)建節(jié)點(diǎn)node->left = nodeleft; //node和左孩子鏈接que.push(nodeleft);//鏈接好的節(jié)點(diǎn)入隊(duì)}//右節(jié)點(diǎn)同樣的方法int rightval = Getinteger(str, k);if (rightval != -1){auto noderight = new TreeNode(rightval);node->right = noderight;que.push(noderight);}}return head; //返回頭結(jié)點(diǎn)
}
4.重建二叉樹(shù)
之前就說(shuō)過(guò)三種遍歷方式:前中后,只有前+后不能構(gòu)建出二叉樹(shù)
同一個(gè)顏色是同一次遞歸
最后根據(jù) 這個(gè)規(guī)律可以得到二叉樹(shù)
TreeNode* _reConstructBinaryTree(vector<int>& pre, vector<int>& vin, int& k, //k一定要給&,在每個(gè)遞歸里是看得見(jiàn)改變的int begin, int end) {if (begin > end) return nullptr; //區(qū)間不成立,說(shuō)明為空int rooti = begin; //rooti記錄中序節(jié)點(diǎn)里面根的下標(biāo)while (rooti <= end) { //根的下標(biāo)肯定在合法區(qū)間里if (vin[rooti] == pre[k]) //在中序數(shù)組里找到根,k記錄每個(gè)根在前序里的下標(biāo)break;++rooti;}//rooti代表根節(jié)點(diǎn)的下標(biāo)//[begin,rooti-1] rooti [rooti+1,end]TreeNode* root = new TreeNode(pre[k++]); //創(chuàng)建節(jié)點(diǎn)root->left =_reConstructBinaryTree(pre, vin, k, begin, rooti - 1); //左孩子在左區(qū)間找(因?yàn)橹行蚴亲蟾?#xff09;root->right =_reConstructBinaryTree(pre, vin, k, rooti + 1, end);return root;
}
TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {int k = 0;return _reConstructBinaryTree(pre, vin, k, 0, pre.size() - 1);
}
?5.輸出二叉樹(shù)的右視圖
?根據(jù)給的前序和中序構(gòu)建樹(shù),然后層序思想,每次到一層的最左側(cè),直接入ans
TreeNode* buildtree(vector<int>& xianxu, vector<int>& zhongxu, int& k, //建樹(shù)(和前面重建二叉樹(shù)是一樣的)int begin, int end) {if (begin > end) return nullptr;int rooti = begin;while (rooti <= end) {if (xianxu[k] == zhongxu[rooti])break;++rooti;}TreeNode* root = new TreeNode(xianxu[k++]);root->left = buildtree(xianxu, zhongxu, k, begin, rooti - 1);root->right = buildtree(xianxu, zhongxu, k, rooti + 1, end);return root;
}
void bfs(TreeNode* root, vector<int>& ans) { //層序+找最右節(jié)點(diǎn)if (!root) return;queue<TreeNode*> q;q.push(root);while (!q.empty()) {int size = q.size(); //當(dāng)前層數(shù)的sizewhile (size--) {TreeNode* node = q.front();q.pop();if (size == 0) ans.push_back(node->val); //直到size==0,找到最右節(jié)點(diǎn)if (node->left) q.push(node->left);if (node->right) q.push(node->right);}}
}
vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {// write code herevector<int> ans;int k = 0;TreeNode* root = buildtree(xianxu, zhongxu, k, 0, xianxu.size() - 1);bfs(root, ans);return ans;
}
?但是這樣做總是覺(jué)得很麻煩,所以去評(píng)論區(qū)看來(lái)一下大佬的代碼
void _solve(vector<int> xianxu, vector<int> zhongxu, vector<int>& ans,int level) {if (xianxu.empty()) return; //如果前序是空的,證明根是空if (ans.size() < level) ans.push_back(xianxu[0]); //ans里面的元素個(gè)數(shù)一定是等于層數(shù),如果小于,直接把當(dāng)前的根入elseans[level - 1] = xianxu[0]; //level應(yīng)該也是ans的個(gè)數(shù),最后一個(gè)元素下標(biāo)就是level-1int headpos = 0; //還是找中序里的根while (zhongxu[headpos] != xianxu[0])headpos++;_solve(vector<int>(xianxu.begin() + 1, xianxu.begin() + headpos + 1), vector<int>(zhongxu.begin(), zhongxu.begin() + headpos), ans, level + 1);_solve(vector<int>(xianxu.begin() + headpos + 1, xianxu.end()),vector<int>(zhongxu.begin() + headpos + 1, zhongxu.end()), ans, level + 1);
}
vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {vector<int> ans;_solve(xianxu, zhongxu, ans, 1);return ans;
}
??前面的不解釋了,主要看大佬的遞歸
?之前我們構(gòu)建二叉樹(shù)的時(shí)候只想著找到根節(jié)點(diǎn)的下標(biāo),但是居然沒(méi)有發(fā)現(xiàn)前序begin()+1~begin()+headpos整個(gè)閉區(qū)間是左子樹(shù)的所有節(jié)點(diǎn)!!!!!!!!!!!!!!!
也就是說(shuō)我們之前寫的構(gòu)造二叉樹(shù)的所有步驟都寫麻煩了
來(lái)看前序+中序怎么構(gòu)建二叉樹(shù)
TreeNode* _reConstructBinaryTree(vector<int> pre, vector<int>vin) {if (pre.empty()) return nullptr;int rooti = 0;while (vin[rooti] != pre[0]) {++rooti;}TreeNode* root = new TreeNode(pre[0]);root->left =_reConstructBinaryTree(vector<int>(pre.begin() + 1, pre.begin() + rooti + 1),vector<int>(vin.begin(), vin.begin() + rooti));root->right =_reConstructBinaryTree(vector<int>(pre.begin() + 1 + rooti, pre.end()),vector<int>(vin.begin() + rooti + 1, vin.end()));return root;
}
TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {return _reConstructBinaryTree(pre, vin);
}
6.組隊(duì)競(jìng)賽
這個(gè)題不在面試必刷101,作為補(bǔ)充
一道簡(jiǎn)單的數(shù)學(xué)題
其實(shí)沒(méi)啥好說(shuō)的,先排序,最小的節(jié)點(diǎn)就是前n個(gè),n是隊(duì)伍的個(gè)數(shù),也就代表了如果想讓所有隊(duì)伍的能力值和最大,必須每個(gè)隊(duì)伍有一個(gè)重排v之后的前n個(gè)數(shù)之一
比如
n=2
排序之后前兩個(gè)數(shù)1 2,應(yīng)該給每個(gè)隊(duì)伍分配一個(gè),不能讓1 2同時(shí)出現(xiàn)在一個(gè)隊(duì)伍里
所以sum求和的時(shí)候i從n開(kāi)始,不應(yīng)該直接挨著取n之后的元素,因?yàn)槟惆炎畲蟮囊恍?shù)全部沒(méi)取到,應(yīng)該跳兩個(gè)取一次?
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{int n;while (cin >> n){vector<int> v;v.resize(3 * n);for (int i = 0; i < v.size(); i++){cin >> v[i];}sort(v.begin(), v.end());long long sum = 0;for (int i = n;i < v.size(); i += 2){sum += v[i];}cout << sum<<endl;}return 0;
}
?7.刪除公共字符?
#include <iostream>
#include <string>using namespace std;int main(){string s1, s2;getline(cin, s1);getline(cin, s2);for (int i= 0; i < s1.size(); i++) {if (s2.find(s1[i]) == -1) //在s2中找不到這個(gè)字符則輸出cout << s1[i];}return 0;}
?這個(gè)不是我自己最初寫的,一開(kāi)始是把s2里面先遍歷然后映射到數(shù)組里,但是顯然慢
這個(gè)直接在s2里面找s1是不是在很方便