day7
61.撲克牌中的順子
思路:先將牌排序，然后將牌分為兩部分：0和非0。遍歷非0部分，遇到非順子的情況，消耗掉一個(gè)0，并自加1。最后看看非0部分能否遍歷完畢。
class Solution {
public:
bool isStraight(vector<int>& nums) {
sort(nums.begin(),nums.end());
int zero=-1;//指向最后一個(gè)零元素,不存在的話為-1
int k,n=nums.size();
for(k=0;nums[k]==0&&k<nums.size();k++){//nums[k]==0一定要寫在前面
}
if(k) zero+=k;
int i=0,j=zero+1;
while(j<nums.size()-1){
if(nums[j+1]-nums[j]==1){
j++;
}
else{
if(i<=zero){
I++;
//nums[j+1]--;不可以這樣寫,這樣會(huì)影響到j(luò)+2 對(duì) j+1的判斷
nums[j]++;
}
else{
break;
}
}
}
if(j==n-1 || j==n || j==nums.size()-1) return true;
else return false;
}
};
課本的思路更加清晰：
首先把數(shù)組排序；其次統(tǒng)計(jì)數(shù)組中0的個(gè)數(shù)；最后統(tǒng)計(jì)排序之后的數(shù)組中相鄰數(shù)字之間的空缺總數(shù)。如果空缺的總數(shù)小于或者等于0的個(gè)數(shù)，那么這個(gè)數(shù)組就是連續(xù)的；反之，則不連續(xù)。但需要注意：如果數(shù)組中的非0數(shù)字重復(fù)出現(xiàn)，則該數(shù)組不是連續(xù)的。也就是說(shuō)，如果牌中有對(duì)子，則不可能是順子。
課本說(shuō)，sort函數(shù)為o(nlogn)，還不夠快。由于撲克牌的值出現(xiàn)在0~13之間，我們可以定義一個(gè)長(zhǎng)度為14的哈希表，這樣在O(n)時(shí)間就能完成排序。通常我們認(rèn)為不同級(jí)別的時(shí)間復(fù)雜度只有當(dāng)n足夠大時(shí)才有意義。由于本題中數(shù)組的長(zhǎng)度是固定的，只有5張牌，那么O(n)和O(nlogn)不會(huì)有多少區(qū)別，我們可以選用簡(jiǎn)潔易懂的方法來(lái)實(shí)現(xiàn)算法。
HASH排序原理：
將Value值作為下標(biāo)，存放在一個(gè)conut數(shù)組里面。以count數(shù)組對(duì)應(yīng)下標(biāo)的值為計(jì)重復(fù)次數(shù)。遍歷count數(shù)組。對(duì)有值的進(jìn)行打印下標(biāo)。完成排序。整體的時(shí)間復(fù)雜度取決于數(shù)組最大數(shù)字
測(cè)試了好多次代碼才通過(guò)
class Solution {
public:
bool isStraight(vector<int>& nums) {
sort(nums.begin(),nums.end());
int zero=0,blank=0;//0的數(shù)目和空缺數(shù)
for(int i=0;i<nums.size()-1;i++){
if(nums[i]==0){
zero++;
}
else if(nums[i]==nums[i+1]){
return false;
}
else{
blank+=nums[i+1]-nums[i]-1;//+=!
}
}
if(blank<=zero||blank==0) return true;//不是blank==zero
else return false;
}
};
課本的寫法
class Solution {
public:
bool isStraight(vector<int>& nums) {
sort(nums.begin(),nums.end());
int zero=0,gap=0;
for(int i=0;nums[i]==0&&i<nums.size();i++){
zero++;
}
for(int i=zero;i<nums.size()-1;i++){
if(nums[i]==nums[i+1]){
return false;
}
gap+=nums[i+1]-nums[i]-1;
}
if(gap<=zero) return true;//不是blank==zero
else return false;
}
};
思路2:關(guān)鍵點(diǎn)在于max-min<5
https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/solution/mian-shi-ti-61-bu-ke-pai-zhong-de-shun-zi-ji-he-se/
未實(shí)現(xiàn)
62.圓圈中最后剩下的數(shù)字(重點(diǎn))
思路1:環(huán)形鏈表模擬圓圈
題目中有一個(gè)數(shù)字圓圈，很自然的想法就是用個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)模擬這個(gè)圓圈。
在常用的數(shù)據(jù)結(jié)構(gòu)中，很容易的想到環(huán)形鏈表?？梢詣?chuàng)建一個(gè)共有n個(gè)結(jié)點(diǎn)的環(huán)形鏈表，然后每次都從這個(gè)鏈表中刪除第m個(gè)結(jié)點(diǎn)。
一開始個(gè)人的思路是用數(shù)組，但數(shù)組不適合頻繁的刪除操作啊。
如果面試官要求不可以使用標(biāo)準(zhǔn)模版庫(kù)里的數(shù)據(jù)容器來(lái)模擬環(huán)形鏈表，那么我們可以自己實(shí)現(xiàn)一個(gè)鏈表。若沒有要求可以使用模版庫(kù)中的std::list(雙向鏈表)來(lái)模擬一個(gè)環(huán)形鏈表。由于list并不是一個(gè)環(huán)形結(jié)構(gòu)，因此每當(dāng)?shù)鲯呙璧芥湵砟┪矔r(shí)，要記得把迭代器移到鏈表的頭部。這樣就相當(dāng)于按照順序在一個(gè)圓圈里遍歷了。
雖然超時(shí)了，但是這個(gè)思路要會(huì)。
class Solution {
public:
int lastRemaining(int n, int m) {
list<int> cir;
for(int i=0;i<n;i++){
cir.push_back(i);
}
list<int>::iterator cur=cir.begin();
while(cir.size()>1){
for(int i=1;i<m;i++){
cur++;
if(cur==cir.end()) cur=cir.begin();
}
list<int>::iterator next=++cur;
if(next==cir.end()) next=cir.begin();
--cur;
cir.erase(cur);
cur=next;
}
return cir.back();
}
};
自己寫的代碼，原本想利用求余來(lái)節(jié)約時(shí)間，可是忽略了余數(shù)的結(jié)果范圍是0～cir.size()-1;當(dāng)余數(shù)為0時(shí)，應(yīng)該令其等于cir.size();
否則你后續(xù)的while(--temp_m) 根本無(wú)法退出循環(huán)，即使修改成while(--temp_m>0)也是不對(duì)的，雖然可以退出循環(huán)，但是也是不正確的。
class Solution {
public:
int lastRemaining(int n, int m) {
list<int> cir;
for(int i=0;i<n;i++){
cir.push_back(i);
}
list<int>::iterator cur=cir.begin();
while(cir.size()>1){
int temp_m=m%cir.size();
if(temp_m==0) temp_m=cir.size();//!
while(--temp_m){//0如果減1 變成-1 負(fù)數(shù)一直剪也不會(huì)變成0呀.。
//while(--temp_m>0){
cur++;
if(cur==cir.end()) cur=cir.begin();
}
list<int>::iterator next=++cur;
if(next==cir.end()) next=cir.begin();
--cur;
cir.erase(cur);
cur=next;
}
return cir.back();
}
};
ps:list的迭代器erase問題
https://www.cnblogs.com/litifeng/p/12960622.html
一開始的思路是數(shù)組，但是寫不出來(lái)代碼，寫得很復(fù)雜，還用什么迭代器，都暈了，看看別人的，好好領(lǐng)悟一下
class Solution{
public:
//n個(gè)數(shù)字，每次刪除第m個(gè)數(shù)字
int lastRemaining(int n, int m){
if (n < 1 || m < 1) return -1;
//使用vector來(lái)模擬一個(gè)環(huán)形鏈表
vector<int> num(n);
for(int i = 0; i < n; i++) num[i] = i;
int temp = 0;
while(num.size() > 1){
int count = temp + m - 1;//從數(shù)組開頭刪除下一個(gè)節(jié)點(diǎn)需要的總步數(shù)
int size = num.size();//數(shù)組大小
int mv = count % size;//實(shí)際從數(shù)組開頭需走的步數(shù)
temp = mv;
num.erase(num.begin() + mv); //刪除元素
}
return num[0];
}
};
思路2:
課本p302-303
沒有實(shí)現(xiàn) 沒有仔細(xì)去想
下面應(yīng)該都是思路2
https://blog.csdn.net/u011500062/article/details/72855826
https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/huan-ge-jiao-du-ju-li-jie-jue-yue-se-fu-huan-by-as/
https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-by-lee/
https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/javajie-jue-yue-se-fu-huan-wen-ti-gao-su-ni-wei-sh/
https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/jian-zhi-offer-62-yuan-quan-zhong-zui-ho-dcow/
63.股票的最大利潤(rùn)
思路：
買入價(jià)越低越好，賣出價(jià)越高越好。
自己的思路：遍歷兩次。先從后往前遍歷，建立max_n數(shù)組，表示i之后的最大賣出價(jià)。
第二次從頭遍歷，求每一個(gè)買入價(jià)和賣出價(jià)的差，找出最大值。
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size()<1) return 0;
vector<int> max_p(prices.size());
int max=-1;//價(jià)格不會(huì)為負(fù)數(shù)
for(int i=prices.size()-1;i>=0;i--){
if(prices[i]>max){
max=prices[i];
}
max_p[i]=max;
}
int ans=0;
int min=prices[0];
for(int i=1;i<prices.size();i++){
if(prices[i]<min) min=prices[i];
if(max_p[i]-min>ans) ans=max_p[i]-min;
}
return ans;
}
};
優(yōu)化：實(shí)際上并不需要遍歷兩次，也不需建立數(shù)組。
定義函數(shù)diff(i)為當(dāng)賣出價(jià)為數(shù)組中第i個(gè)數(shù)字時(shí)可能獲得的最大利潤(rùn)。
顯然，當(dāng)賣出價(jià)固定時(shí)，買入價(jià)越低獲得的利潤(rùn)越大。也就是說(shuō)，如果在掃描到數(shù)組中的第i個(gè)數(shù)字時(shí)，只要我們能記住之前的i-1個(gè)數(shù)字中的最小值，就能算出在當(dāng)前價(jià)位賣出時(shí)可能得到的最大利潤(rùn)!!!
代碼中變量min保存了數(shù)組前i-1個(gè)數(shù)字的最小值，也就是之前股票的最低價(jià)。只遍歷一次，時(shí)間復(fù)雜度o(n)
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size()<=1) return 0;
int min_price=prices[0],max_profit=0;
for(int i=1;i<prices.size();i++){
if(prices[i]<min_price){
min_price=prices[i];
}
int cur_profit=prices[i]-min_price;
if(cur_profit>max_profit){
max_profit=cur_profit;
}
}
return max_profit;
}
};
64.求1+2+...+n(重點(diǎn))
不會(huì)寫
通常求1+2+…+n除了用公式n(n+1)/2之外，無(wú)外乎循環(huán)和遞歸兩種思路。由于已經(jīng)明確限制for和while的使用，循環(huán)已經(jīng)不能再用了。同樣，遞歸函數(shù)也需要用if語(yǔ)句或者條件判斷語(yǔ)句來(lái)判斷是繼續(xù)遞歸下去還是終止遞歸，但現(xiàn)在題目已經(jīng)不允許使用這兩種語(yǔ)句了
因此我們手里能用的工具很少，列舉出來(lái)發(fā)現(xiàn)只有加減法、賦值、位運(yùn)算符以及邏輯運(yùn)算符。
遞歸(沒有想到)：f(n)=n+f(n-1)
class Solution {
public:
int sumNums(int n) {
if(n==1) return 1;
return n+sumNums(n-1);
}
};
但是這道題：不能用for循環(huán);不能用if運(yùn)算.
如何解決：
for用遞歸實(shí)現(xiàn)，這很好理解
if用邏輯運(yùn)算符的計(jì)算特性來(lái)解決。即&&的短路特性。
A && function() 如果A是True， 返回的是function 如果A是false，function都不會(huì)被執(zhí)行到就下一句了。
因此我們把遞歸入口放在function處，那么A表達(dá)式就可以起到if的作用，function遞歸起到for的作用
為了讓n能及時(shí)停止（數(shù)量夠的時(shí)候，要輸出false），我們只能把終點(diǎn)設(shè)置成0，因此我們遞歸中要倒數(shù)。
class Solution {
public:
int sumNums(int n) {
n && (n += sumNums(n-1));
return n;
}
};
時(shí)間復(fù)雜度：O(n)遞歸函數(shù)遞歸n 次，每次遞歸中計(jì)算時(shí)間復(fù)雜度為 O(1)，因此總時(shí)間復(fù)雜度為 O(n)。
空間復(fù)雜度：O(n)。遞歸函數(shù)的空間復(fù)雜度取決于遞歸調(diào)用棧的深度，這里遞歸函數(shù)調(diào)用棧深度為 O(n)，因此空間復(fù)雜度為 O(n)。
思路2:巧用sizeof做乘法，>>做除法
定義一個(gè)二維數(shù)組再獲取數(shù)組的size，達(dá)到n*(n+1)的目的，然后位運(yùn)算就是n(n+1)/2
class Solution {
public:
int sumNums(int n) {
bool arr[n][n+1];
return sizeof(arr)>>1;
}
};
思路3 .4.5.6:利用構(gòu)造函數(shù)/虛函數(shù)/函數(shù)指針/模版類型求解
課本p307-310
由于不熟悉這些知識(shí)，不太看得明白
67.把字符串轉(zhuǎn)變?yōu)檎麛?shù)
(重點(diǎn)res=res*10+str[i]-'0',不必按照思維從低位算起)
原始思路：常規(guī)的思路，逐步解決，具體如步驟1、2、3。
但是22% 5%..
class Solution {
public:
int strToInt(string str) {
if(str.empty()) return 0;//空字符串
//1 去除開頭的空格
int i=0;
while(i<str.size()&&str[i]==' '){
i++;
}
if(i==str.size()) return 0;//全為空格
if(str[i]!='+' && str[i]!='-' && str[i]<'0' && str[i]>'9'){
return 0;
}
//2 判斷正負(fù)
bool positive=true;
if(str[i]=='+') i++;
else if(str[i]=='-'){
i++;
positive=false;
}
//3 處理數(shù)字并返回結(jié)果
if(i==str.size()) return 0;//只有正負(fù)號(hào)
//去除開頭的無(wú)意義0
while(i<str.size()&&str[i]=='0'){
i++;
}
if(i==str.size()) return 0;//全是0
stack<int> num;
while(i<str.size()&&str[i]>='0'&&str[i]<='9'){
num.push(str[i]-'0');
i++;
}
long n=0,ten=1;
while(!num.empty()){
n+=num.top()*ten;
num.pop();
ten*=10;
//如果不去除開頭的無(wú)意義0，雖然n沒有超過(guò)INT_MAX，不會(huì)break，但是ten*=10這里會(huì)不斷累乘，導(dǎo)致溢出 程序崩潰
//" 0000000000012345678"
if(n>INT_MAX) break;
if(ten>10000000000) break;
//"20000000000000000000"
//n一直沒有超過(guò)INT_MAX，不會(huì)break，但是ten*=10這里不斷累乘，導(dǎo)致溢出 程序崩潰。而且開頭沒有無(wú)意義的0
}
if(!positive) n=-n;
if(n>INT_MAX || (!num.empty()&&positive)){
return INT_MAX;
}
else if(n<INT_MIN || (!num.empty()&&!positive)){
return INT_MIN;
}
else{
return (int)n;
}
}
};
自己的代碼因?yàn)闆]有使用正確的思想將string轉(zhuǎn)為int導(dǎo)致復(fù)雜。
改成：res=res*10+str[i]-'0';
幾乎雙百
class Solution {
public:
int strToInt(string str) {
if(str.empty()) return 0;//空字符串
//1 去除開頭的空格
int i=0;
while(i<str.size()&&str[i]==' '){
i++;
}
if(i==str.size()) return 0;//全為空格
if(str[i]!='+' && str[i]!='-' && str[i]<'0' && str[i]>'9'){
return 0;
}
//2 判斷正負(fù)
bool positive=true;
if(str[i]=='+') i++;
else if(str[i]=='-'){
i++;
positive=false;
}
//3 處理數(shù)字并返回結(jié)果
if(i==str.size()) return 0;//只有正負(fù)號(hào)
long res=0;
while(i<str.size()&&str[i]>='0'&&str[i]<='9'){
res=res*10+str[i]-'0';
i++;
if(res>INT_MAX) break;
}
if(!positive) res=-res;
if(res>INT_MAX){
return INT_MAX;
}
else if(res<INT_MIN){
return INT_MIN;
}
else{
return (int)res;
}
}
};
但是好像不能夠使用long..因?yàn)轭}目說(shuō)環(huán)境是32位的.
下次再看吧.
https://leetcode-cn.com/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/solution/mian-shi-ti-67-ba-zi-fu-chuan-zhuan-huan-cheng-z-4/
68- I. 二叉搜索樹的最近公共祖先
思路1：注意是BST，所以分別保存兩個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)到數(shù)組，最后從數(shù)組尾部開始遍歷，尋找第一個(gè)相同節(jié)點(diǎn)。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> phead,qhead;
TreeNode* temp=root;
//保存p的父親節(jié)點(diǎn)
while(temp!=p){
if(temp->val>p->val){
temp=temp->left;
}
else if(temp->val<p->val){
temp=temp->right;
}
else{
temp=p;
}
phead.push_back(temp);
}
//保存q的父親節(jié)點(diǎn)
temp=root;
while(temp!=q){
if(temp->val>q->val){
temp=temp->left;
}
else if(temp->val<q->val){
temp=temp->right;
}
else{
temp=q;
}
qhead.push_back(temp);
}
//從尾部開始找第一個(gè)相同的元素
for(int i=phead.size()-1;i>=0;i--){
for(int j=qhead.size()-1;j>=0;j--){
if(phead[i]==qhead[j]){
return phead[i];
}
}
}
return root;
}
};
標(biāo)準(zhǔn)思路：其實(shí)并不需要這么復(fù)雜。利用bst的性質(zhì)：位于左子樹的節(jié)點(diǎn)都比父節(jié)點(diǎn)小，而位于右子樹的節(jié)點(diǎn)都比父節(jié)點(diǎn)大。我們只需從樹的根結(jié)點(diǎn)開始和輸入的兩個(gè)結(jié)點(diǎn)進(jìn)行比較。如果當(dāng)前結(jié)點(diǎn)的值比兩個(gè)結(jié)點(diǎn)的值都大，那么最低的共同父結(jié)點(diǎn)一定是在當(dāng)前結(jié)點(diǎn)的左子樹中，于是下一步遍歷當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)；如果當(dāng)前結(jié)點(diǎn)的值比兩個(gè)結(jié)點(diǎn)的值都小，那么最低的共同父結(jié)點(diǎn)一定是在當(dāng)前結(jié)點(diǎn)的右子樹中，于是下一步遍歷當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)。這樣在樹中從上到下找到第一個(gè)在輸入結(jié)點(diǎn)的值之間的結(jié)點(diǎn)，就是最低的公共祖先。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==NULL) return NULL;
if (root->val > p->val && root->val > q->val)
return lowestCommonAncestor(root->left, p, q);
if (root->val < p->val && root->val < q->val)
return lowestCommonAncestor(root->right, p, q);
return root;//不滿足兩個(gè)if則找到了，直接返回
}
};
時(shí)間復(fù)雜度 O(N) ： 其中 N 為二叉樹節(jié)點(diǎn)數(shù)；每循環(huán)一輪排除一層，二叉搜索樹的層數(shù)最小為 logN （滿二叉樹），最大為 N （退化為鏈表）。
空間復(fù)雜度 O(N) ： 最差情況下，即樹退化為鏈表時(shí)，遞歸深度達(dá)到樹的層數(shù) N 。
思路2:迭代解法
將上述思想轉(zhuǎn)為迭代
迭代
1.循環(huán)搜索： 當(dāng)節(jié)點(diǎn) root 為空時(shí)跳出；
當(dāng) p,q 都在 root 的 右子樹 中，則遍歷至 root.right ；
否則，當(dāng) p,q 都在 root 的 左子樹 中，則遍歷至 root.left ；
否則，說(shuō)明找到了 最近公共祖先 ，跳出。
- 返回值： 最近公共祖先 root 。
復(fù)雜度分析：
時(shí)間復(fù)雜度 O(N) ： 其中 N 為二叉樹節(jié)點(diǎn)數(shù)；每循環(huán)一輪排除一層，二叉搜索樹的層數(shù)最小為 logN （滿二叉樹），最大為 N （退化為鏈表）。
空間復(fù)雜度 O(1) ： 使用常數(shù)大小的額外空間。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while(root!=NULL){
if(root->val < p->val && root->val < q->val) // p,q 都在 root 的右子樹中
root = root->right; // 遍歷至右子節(jié)點(diǎn)
else if(root->val > p->val && root->val > q->val) // p,q 都在 root 的左子樹中
root = root->left; // 遍歷至左子節(jié)點(diǎn)
else break;
}
return root;
}
};
68 - II. 二叉樹的最近公共祖先
思路：dfs遍歷每一條路徑并臨時(shí)保存，如果發(fā)現(xiàn)該路徑中有所求節(jié)點(diǎn)p or q，就保存下來(lái)，找到兩條路徑之后便退出。
48% 10%
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> path,phead,qhead;
dfs(root,p,q,path,phead,qhead);
//從尾部開始找第一個(gè)相同的元素
for(int i=phead.size()-1;i>=0;i--){
for(int j=qhead.size()-1;j>=0;j--){
if(phead[i]==qhead[j]){
return phead[i];
}
}
}
return root;
}
void dfs(TreeNode* root, TreeNode* p, TreeNode* q,vector<TreeNode*> &path,vector<TreeNode*> &phead,vector<TreeNode*> &qhead){
if(root==NULL|| (!phead.empty()&&!qhead.empty()) ){//如果兩條路徑都找到便不需要再遍歷了
return;
}
path.push_back(root);
if(root->val==q->val){
qhead=path;
}
else if(root->val==p->val){
phead=path;
}
dfs(root->left,p,q,path,phead,qhead);
dfs(root->right,p,q,path,phead,qhead);
path.pop_back();
}
};
其實(shí)獲得兩條路徑之后，并不需要從尾部開始找，從頭也可以，這樣都不用寫兩層循環(huán)了呀，更快。
75% 10%
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> path,phead,qhead;
dfs(root,p,q,path,phead,qhead);
//從頭開始找
TreeNode* res=root;
for(int i=0,j=0;i<phead.size()&&j<qhead.size();i++,j++){
if(phead[i]==qhead[j]){
res=phead[i];
}
}
return res;
}
void dfs(TreeNode* root, TreeNode* p, TreeNode* q,vector<TreeNode*> &path,vector<TreeNode*> &phead,vector<TreeNode*> &qhead){
if(root==NULL|| (!phead.empty()&&!qhead.empty()) ){//如果兩條路徑都找到便不需要再遍歷了
return;
}
path.push_back(root);
if(root->val==q->val){
qhead=path;
}
else if(root->val==p->val){
phead=path;
}
dfs(root->left,p,q,path,phead,qhead);
dfs(root->right,p,q,path,phead,qhead);
path.pop_back();
}
};
另一種思路，遞歸，不用存路徑。
沒太看明白。。
https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/solution/mian-shi-ti-68-ii-er-cha-shu-de-zui-jin-gong-gon-7/
這個(gè)也是這種做法
//如果是一般的二叉樹
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == NULL)
return NULL;
//如果根節(jié)點(diǎn)就是p或者q，返回根節(jié)點(diǎn)
if(root == p || root == q)
return root;
//分別去左右子樹里面找
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if(left && right)//p，q各在一邊，說(shuō)明當(dāng)前的根就是最近共同祖先
return root;
else if(left)//說(shuō)明p，q都在左子樹
return left;
else if(right)//說(shuō)明p，q都在右子樹
return right;
else
return NULL;
}
};
