目錄

1.二叉搜索樹的最近公共祖先

?2.在二叉樹中找到兩個節(jié)點的最近公共祖先

3.序列化二叉樹

4.重建二叉樹

?5.輸出二叉樹的右視圖

6.組隊競賽

?7.刪除公共字符?

---

?

1.二叉搜索樹的最近公共祖先

這是一個簡單的問題，因為是二叉搜索樹（有序），首先看看p，q是不是都在左子樹？右子樹

如果不是，那么現(xiàn)在的根就是兩個的最近公共祖先

  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);//在兩個子樹else return root->val;}

?2.在二叉樹中找到兩個節(jié)點的最近公共祖先

最一般的樹怎么找最近公共祖先？

?最直觀的方法肯定是和上面搜索樹的想法一樣，先看看這兩個節(jié)點是不是在一側的子樹里

但是這不是搜索樹，不可以比較節(jié)點的值來判斷在左子樹/右子樹

沒有條件創(chuàng)造條件也要上，誰讓我想不出來更好的思路....

  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);}

?欣喜若狂的提交，超時！！！！！！！！！！！！！！！！！！！！！！！！！！！！

為什么？

因為在子樹里搜索很浪費時間

?那么只能換方法

記得我們怎么做相交鏈表的題目嗎？

想找到鏈表的交點，那么我們計算兩個鏈表的長度，讓更長的鏈表先走差距（兩個鏈表長度差）步，然后挨個比較目前的val值，找到一樣的就輸出

那你看這個樹枝是不是很像鏈表

所以思路就有了

bool FindPath(TreeNode* root, stack<int>& s, int o) //找到這個節(jié)點的所有祖先
{if (!root) return false; //遇到空節(jié)點肯定不是祖先s.push(root->val); //先把這個節(jié)點入棧if (root->val == o) //找到了目標節(jié)點，直接返回return true;if (FindPath(root->left, s, o))  return true; //在左子樹里找到他，返回trueif (FindPath(root->right, s, o)) return true; //右子樹中找到他，trues.pop(); //走到這說明左/右子樹沒找到這個節(jié)點 ，這個root就不是目標節(jié)點的祖先，popreturn false; //返回在這個路徑?jīng)]找到
}
int lowestCommonAncestor(TreeNode* root, int o1, int o2) {// 兩個棧記錄他們的祖先列表stack<int> s1;stack<int> s2;FindPath(root, s1, o1);FindPath(root, s2, o2);while (s1.size() < s2.size()) //長度不一樣s2.pop(); //更長的popwhile (s1.size() > s2.size())s1.pop();while (s1.top() != s2.top()) //當前不是公共祖先 {//都把這個節(jié)點pops1.pop();s2.pop();}return s1.top(); //或者s2.top() 都一樣的值
}

3.序列化二叉樹

寫兩個函數(shù)，讓字符串可以構建成二叉樹，二叉樹也可以寫成字符串

void dfs_Serialize(TreeNode* root, string& s)
{if (!root)//如果是空節(jié)點，直接寫一個#，空節(jié)點的子節(jié)點被省略，所以直接返回{s += '#';return;}s += to_string(root->val) + ','; //把非空節(jié)點的val變成字符，寫入到字符串dfs_Serialize(root->left, s); //左子樹dfs_Serialize(root->right, s);//右子樹
}
char* Serialize(TreeNode* root) { //用二叉樹寫字符串數(shù)組string s; //首先寫成字符串dfs_Serialize(root, s); //深度優(yōu)先遍歷（前序）char* ans = new char[s.size() + 1]; //最后應該輸出數(shù)組形式，先開數(shù)組（加上1寫'\0')memcpy(ans, s.c_str(), s.size()); //把字符串拷貝給數(shù)組ans[s.size()] = '\0';//終止符return ans;
}
TreeNode* dfs_Deserialize(char*& s) //把字符串變二叉樹，注意這個字符串在遞歸的時候不是每次從頭開始，所以&
{if (*s == '#')//是空節(jié)點的標志，直接返回nullptr{s++; //s向后走一個，因為這個字符對應的節(jié)點已經(jīng)被表示完了return nullptr;}int val = 0; //字符串對應的節(jié)點valwhile (*s != ',') //看樣例，字符串以，分割{val = val * 10 + (*s - '0'); //萬一不是個位數(shù)，需要這樣算好每一位s++;//s往后走}s++; //把逗號跳過TreeNode* root = new TreeNode(val); //用val創(chuàng)建節(jié)點root->left = dfs_Deserialize(s); //左節(jié)點的創(chuàng)建root->right = dfs_Deserialize(s);//右節(jié)點return root; //返回根
}
TreeNode* Deserialize(char* str) {return dfs_Deserialize(str);
}

還有第二個方法，借助隊列，把字符串構建成二叉樹（這個顯然沒有上面的方法快）

char* Serialize(TreeNode* root) { //用層序來寫字符串if (!root) return nullptr; //如果是空節(jié)點，不需要記錄他的孩子string str; queue<TreeNode*> que;que.push(root); //先把根入隊while (!que.empty()){auto node = que.front(); //取隊頭元素que.pop();if (node) //取出的節(jié)點不是空{str += to_string(node->val) + ","; //字符串保存這個節(jié)點val對應的字符，并且在字符串里面寫入分割符號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)  //把字符轉化成數(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; //記錄字符串的下標queue<TreeNode* > que;auto head = new TreeNode(Getinteger(str, k)); //一定要把字符串下標也傳，要不然找不到位置了que.push(head); //把頭結點入隊while (!que.empty()){auto node = que.front();//隊頭que.pop();//這里的反序列化是根據(jù)前序用字符串構建二叉樹int leftval = Getinteger(str, k); //把字符串轉換成左節(jié)點的valif (leftval != -1)//如果左孩子的val是-1，代表是空節(jié)點{//不是空auto nodeleft = new TreeNode(leftval) ;//創(chuàng)建節(jié)點node->left = nodeleft; //node和左孩子鏈接que.push(nodeleft);//鏈接好的節(jié)點入隊}//右節(jié)點同樣的方法int rightval = Getinteger(str, k);if (rightval != -1){auto noderight = new TreeNode(rightval);node->right = noderight;que.push(noderight);}}return head; //返回頭結點
}

4.重建二叉樹

之前就說過三種遍歷方式：前中后，只有前+后不能構建出二叉樹

同一個顏色是同一次遞歸

最后根據(jù) 這個規(guī)律可以得到二叉樹

TreeNode* _reConstructBinaryTree(vector<int>& pre, vector<int>& vin, int& k, //k一定要給&，在每個遞歸里是看得見改變的int begin, int end) {if (begin > end) return nullptr;  //區(qū)間不成立，說明為空int rooti = begin; //rooti記錄中序節(jié)點里面根的下標while (rooti <= end) { //根的下標肯定在合法區(qū)間里if (vin[rooti] == pre[k]) //在中序數(shù)組里找到根，k記錄每個根在前序里的下標break;++rooti;}//rooti代表根節(jié)點的下標//[begin,rooti-1] rooti [rooti+1,end]TreeNode* root = new TreeNode(pre[k++]); //創(chuàng)建節(jié)點root->left =_reConstructBinaryTree(pre, vin, k, begin, rooti - 1); //左孩子在左區(qū)間找（因為中序是左根右）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.輸出二叉樹的右視圖

?根據(jù)給的前序和中序構建樹，然后層序思想，每次到一層的最左側，直接入ans

TreeNode* buildtree(vector<int>& xianxu, vector<int>& zhongxu, int& k, //建樹（和前面重建二叉樹是一樣的）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é)點if (!root) return;queue<TreeNode*> q;q.push(root);while (!q.empty()) {int size = q.size(); //當前層數(shù)的sizewhile (size--) {TreeNode* node = q.front();q.pop();if (size == 0) ans.push_back(node->val);  //直到size==0，找到最右節(jié)點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;
}

?但是這樣做總是覺得很麻煩，所以去評論區(qū)看來一下大佬的代碼

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里面的元素個數(shù)一定是等于層數(shù)，如果小于，直接把當前的根入elseans[level - 1] = xianxu[0]; //level應該也是ans的個數(shù)，最后一個元素下標就是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;
}

??前面的不解釋了，主要看大佬的遞歸

?之前我們構建二叉樹的時候只想著找到根節(jié)點的下標，但是居然沒有發(fā)現(xiàn)前序begin（）+1~begin（）+headpos整個閉區(qū)間是左子樹的所有節(jié)點！！！！！！！！！！！！！！！

也就是說我們之前寫的構造二叉樹的所有步驟都寫麻煩了

來看前序+中序怎么構建二叉樹

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.組隊競賽

這個題不在面試必刷101，作為補充

一道簡單的數(shù)學題

其實沒啥好說的，先排序，最小的節(jié)點就是前n個，n是隊伍的個數(shù)，也就代表了如果想讓所有隊伍的能力值和最大，必須每個隊伍有一個重排v之后的前n個數(shù)之一

比如

n=2

排序之后前兩個數(shù)1 2，應該給每個隊伍分配一個，不能讓1 2同時出現(xiàn)在一個隊伍里

所以sum求和的時候i從n開始，不應該直接挨著取n之后的元素，因為你把最大的一些數(shù)全部沒取到，應該跳兩個取一次?

#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中找不到這個字符則輸出cout << s1[i];}return 0;}

?這個不是我自己最初寫的，一開始是把s2里面先遍歷然后映射到數(shù)組里，但是顯然慢

這個直接在s2里面找s1是不是在很方便