八皇后
题目：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
想法1：一层层来放置。
代码1：
int que[8]={-1,-1,-1,-1,-1,-1,-1,-1};
int cou=0;
bool avl(int i,int j){
for(int m =0; m<i;m++){
if(que[m]==j) return false;
if((m-i)==(que[m]-j)) return false;
if((m-i)==(j-que[m])) return false;
}
return true;
}
void fin(int cow){
for(int i = 0;i<8;i++){
que[cow]=i;
if(avl(cow,i)){
if(cow==7){//如果八个皇后都放满了统计一下
for(int i = 0 ; i<8;i++){
cout<<que[i];
}
cout<<" "<<endl;
cou++;
}
fin(cow+1);
}
}
return;
}
结果1：
92种方法。
剪绳子
题目：给你一根长度为n绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1）。每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0] * k[1]…k[m]可能的最大乘积是多少？例如当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到最大的乘积18。
我的：不会
int cut(int length) {
if(length<2) return 0;
if(length<4) return length-1;
vector<int> temp;
temp.push_back(0);
temp.push_back(1);
temp.push_back(2);
temp.push_back(3);
for(int i = 4 ;i<=length;i++){
int ma = 0;
for(int j = 1 ;j<=length/2;j++){
ma = max(temp[j]*temp[i-j],ma);
}
temp.push_back(ma);
}
return temp.back();
}
剑指：动态规划
动态规划求解问题的四个特征：
①求一个问题的最优解；
②整体的问题的最优解是依赖于各个子问题的最优解；
③小问题之间还有相互重叠的更小的子问题；
④从上往下分析问题，从下往上求解问题；
"""
在剪绳子这个题目中，由于必须要剪一刀，因此会导致当所给的绳子长度是小于4的时候，剪完之后的长度
小于剪之前的长度。但是我们在递推的时候，例如求f(5) = max{f(1)*f(4), f(2)*f(3)} = 6
如果令f(3)=2的话，将导致递推公式错误，因此，对于小于4的输入，我们特殊处理。
注意不符合切割条件的输入n，以及输入为2、3长度时的结果，因为题中规定m>1。
"""
//输入绳子的长度,输出最大乘积
int maxProductAfterCutting_solution1(int length) {
if(length < 2)//因为要求长度n>1,所以这里返回0表示输入非法
return 0;
if(length == 2)//长度为2时,因为要求剪下段数m>1,所以最大是1x1=1
return 1;
if(length == 3)//长度为3时,因为要求剪下段数m>1,所以最大是1x2=2
return 2;
//运行至此,说明绳子的长度是>3的,这之后0/1/2/3这种子问题最大就是其自身长度
//而不再需要考虑剪一刀的问题,因为它们剪一刀没有不剪来的收益高
//而在当下这么长的绳子上剪过才可能生成0/1/2/3这种长度的绳子,它们不需要再减
//所以下面的表中可以看到它们作为子问题的值和上面实际返回的是不一样的
//在表中先打上子绳子的最大乘积
int* products = new int[length + 1];
products[0] = 0;
products[1] = 1;
products[2] = 2;
products[3] = 3;//到3为止都是不剪最好
int max = 0;//用于记录最大乘积
//对于4以上的情况,每次循环要求f(i)
for(int i = 4; i <= length; ++i) {
max = 0;//每次将最大乘积清空
//因为要计算f(j)乘以f(i-j)的最大值,j超过i的一半时是重复计算
//所以只需要考虑j不超过i的一半的情况
for(int j = 1; j <= i / 2; ++j) {
//计算f(j)乘以f(i-j)
int product = products[j] * products[i - j];
//如果比当前找到的还大
if(max < product)
max = product;//就把最大值更新
}
//这里是循环无关的,书上在for里面,我把它提出来
products[i] = max;//最终,更新表中的f(i)=max(f(j)·f(i-j))
}
//循环结束后,所求的f(length)也就求出来了
max = products[length];//将其记录下来以在销毁后能返回
delete[] products;//销毁打表的辅助空间
return max;
}
打印从1到最大的n位数
题目：
输入数字n，按顺序打印出从1到最大的n位十进制数。比如输入3，则打印出1、2、3一直到最大的3位数即999。
我的：
//方法1：
void print(int n) {
int ma = 0;
while(n!=0){
ma = ma*10+9;
n--;
}
for(int i = 1 ;i<=ma;i++){
cout<<i<<endl;
}
}
//方法2：全排列
vector<string> result;
void all(int index, int n,string temp){
if(index>n)
{
result.push_back(temp);
return;
}
for(int i = 0;i<10;i++){
string temp2 = temp+char('0'+i);
all(index+1,n,temp2);
}
}
void print(int n) {
string str = "";
all(1,n,str);
string s;
for(int j = 1 ;j<result.size();j++){
s = result[j];
bool flag = false;
int i = 0;
while(i<n){
if(!flag){
if(s[i]!='0'){
flag = true;
cout<<s[i];
}
}else{
cout<<s[i];
}
i++;
}
cout<<""<<endl;
}
}
剑指：
//模拟加法：
class Solution {
public:
void Print1ToMaxOfNDigits(int n)
{
char* number = new char[n + 1];
//开辟一个存放字符数组(包含n + 1个元素 number[0]~number[n])的空间，返回字符数组首元素的地址
memset(number, '0', n); // number[0]~number[n-1]都是'0'
number[n] = '\0';
while (!Increment(number))
{
PrintNumber(number);
}
}
private:
bool Increment(char* number)
{
//此函数用于在表示数字的字符串上 + 1，并判断有没有溢出
//number是一个字符串
bool isOverflow = false; //溢出
int nTackOver = 0; //进位标志
int nLength = strlen(number); //计算字符串str 的长度，直到空结束字符
// number[nLength - 1]是这个数字的倒数第1位
for (int i = nLength - 1; i >= 0; i--)
{
int nSum = number[i] - '0' + nTackOver;
if (i == nLength - 1)
nSum++; //如果是个位（最后一位）的话，+1
if (nSum >= 10)
if (i == 0)
isOverflow = true; //如果nSum==10,且是最高位，则溢出
else
{
nSum -= 10;
nTackOver = 1; //进位
number[i] = '0' + nSum;
}
else
{
number[i] = '0' + nSum;
break; //运行到某一数位不需要进位，退出循环
// 例如520+1之后个位 nSum < 10,此时不会产生进位，也不会有溢出的情况
//可以直接退出循环
}
}
return isOverflow;
}
void PrintNumber(char* number) //此函数用于打印数字，数字前面补位的“0”不打印
{
bool isBeginning0 = true;
int nLength = strlen(number);
for (int i = 0; i < nLength; i++)
{
if (isBeginning0 && number[i] != '0')//开始不为0，第i位不是0
isBeginning0 = false; //例如“00098”到number[2]才不是0,两个条件都为true
//isBeginning0 = false
if (!isBeginning0) //isBeginning0 = false才能执行输出
cout << number[i];
}
cout << endl;
}
};
//全排序：
class Solution {
public:
void Print1ToMaxOfNDigits(int n)
{
char* number = new char[n + 1];
//开辟一个存放字符数组(包含n + 1个元素 number[0]~number[n])的空间，返回字符数组首元素的地址
memset(number, '0', n); // number[0]~number[n-1]都是'0'
number[n] = '\0';
dfsHelper(number, 0, n);
}
private:
void PrintNumber(char* number) //此函数用于打印数字，数字前面补位的“0”不打印
{
bool isBeginning0 = true;
int nLength = strlen(number);
for (int i = 0; i < nLength; i++)
{
if (isBeginning0 && number[i] != '0')//开始不为0，第i位不是0
isBeginning0 = false; //例如“00098”到number[2]才不是0,两个条件都为true
//isBeginning0 = false
if (!isBeginning0) //isBeginning0 = false才能执行输出
cout << number[i];
}
cout << endl;
}
void dfsHelper(char* number, int index, int n)
{
if (index == n)
{
PrintNumber(number);
return;
}
for (int i = 0; i < 10; i++)
{
number[index] = i + '0';
dfsHelper(number, index + 1, n);
}
}
};
删除链表的节点
题目：在O（1）时间内删除链表节点。
我的：遍历在删除是O（N）
由于给出了所要删除结点指针，所以可以直接考虑用删除结点的下一结点代替要删除的结点，然后释放要删除结点的下一个结点。这里得注意的是需要考虑要删除结点的三种情况：1.要删除的节点不是尾节点，2.链表只有一个节点，删除头结点（也是尾节点）3.链表中有多个节点，删除尾结点（这里的情况就蜕变成一般从头到尾遍历寻找要删除的节点的思路，开始没注意到给出要删除的结点的指针已经给出，考虑到了这个O(N）算法...）
剑指：
void DeletNode(ListNode** pListHead,ListNode* pToBeDeleted)//传递二级指针的原因，可能会修改头节点
{
if(!pListHead||pToBeDeleted)
return;
//要删除的节点不是尾节点
if(pToBeDeleted->m_pNext!=nullptr)
{
ListNode* pNext=pToBeDeleted->m_pNext;
pToBeDeleted->m_nValue=pNext->m_nValue;
pToBeDeleted->m_pNext=pNext->m_pNext;
delete pNext;
pNext=nullptr;
}
//链表只有一个节点，删除头节点（也是尾节点）
else if(*pListHead==pToBeDeleted)
{
delete pToBeDeleted;
pToBeDeleted=nullptr;
*pListHead=nullptr;
}
//链表中有多个节点，删除尾节点
else
{
ListNode* pNode=*pListHead;
while(pNode->m_pNext!=pToBeDeleted)
{
pNode=pNode->m_pNext;
}
pNode->m_pNext=nullptr;
delete pToBeDeleted;
pToBeDeleted=nullptr;
}
数字序列中某一位的数字
题目：
数字以01234567891011121314...的格式排列。在这个序列中，第5位（从0开始计）是5，第13位是1，第19位是4。求任意第n为对应的数字。
我的：
int num(int n){
if(n==0) return 0;
if(n==1) return 10;
return (pow(10,n)-pow(10,n-1))*n;
}
void test(int index) {
int n = 0;
int sum = 0;
while(index+1>sum){
sum+=num(++n);
}
sum = 0;
int temp = n-1;
while(temp>0){
sum+=num(temp--);
}
int temp2;
if(n==1) temp2 = (index-sum)/n;
else temp2 = pow(10,n-1)+(index-sum)/n;
cout<<to_string(temp2)[index%n]<<endl;
}
//方法2：
int num(int n){
if(n==0) return 0;
if(n==1) return 10;
return (pow(10,n)-pow(10,n-1))*n;
}
void test(int index) {
int n = 0;
int sum = 0;
while(index+1>sum){
sum+=num(++n);
}
sum = 0;
int temp = n-1;
while(temp>0){
sum+=num(temp--);
}
int temp2;
if(n==1) temp2 = (index-sum)/n;
else temp2 = pow(10,n-1)+(index-sum)/n;
for(int i = 0;i<n-index%n-1;i++){
temp2=temp2/10;
}
temp2=temp2%10;
cout<<temp2<<endl;
}
剑指：
以第15位数字2为例（2隶属与12，两位数，位于12从左侧以0号开始下标为1的位置）
步骤1：首先确定该数字是属于几位数的;
如果是一位数，n<9;如果是两位数，n<9+90*2=189;
说明是两位数。
步骤2：确定该数字属于哪个数。10+(15-10)/2= 12。
步骤3：确定是该数中哪一位。15-10-(12-10)*2 = 1, 所以位于“12”的下标为1的位置，即数字2。
以第1001位数字7为例
步骤1：首先确定该数字是属于几位数的;
如果是一位数，n<9;如果是两位数，n<9+90*2=189;如果是三位数，n<189+900*3=2889;
说明是三位数。
步骤2：确定该数字属于哪个数。100+(1001-190)/3= 370。
步骤3：确定是该数中哪一位。1001-190-(370-100)*3 = 1,所以位于“370”的下标为1的位置，即数字7。
礼物的最大值
题目：
在一个 m*n 的棋盘中的每一个格都放一个礼物，每个礼物都有一定的价值（价值大于0）.你可以从棋盘的左上角开始拿各种里的礼物，并每次向左或者向下移动一格，直到到达棋盘的右下角。给定一个棋盘及上面个的礼物，请计算你最多能拿走多少价值的礼物？
比如说现在有一个如下的棋盘，
image.png
在这个棋盘中，按照（1，12，5，7，7，16，5）的顺序可以拿到总价值最大的礼物。
image.png
我的：
//方法1：
int ma = 0;
void dp(vector<vector<int>> in , int nrows, int ncols,int rows, int cols, int sum){
if(nrows>rows-1||ncols>cols-1) return;
if(nrows==rows-1&&ncols==cols-1) {
sum+=in[nrows][ncols];
ma = max(ma, sum);
return;
}
sum+=in[nrows][ncols];
dp(in, nrows+1,ncols,rows,cols,sum);
dp(in, nrows,ncols+1,rows,cols,sum);
}
void test(vector<vector<int>> in , int rows, int cols) {
int sum = 0;
dp(in, 0,0,rows,cols,sum);
cout<<ma<<endl;
}
//方法2：每个格子等于max（左，上）+本身，而且只用维护一维列长的数组，保存结果。
int test(vector<vector<int>> in , int rows, int cols) {
if(rows==0||cols==0) return 0;
int result = 0;
vector<int> flag(cols,0);
int temp = 0;
flag[0] = in[0][0];
for(int i = 0 ;i<rows;i++){
for(int j = 0 ;j<cols;j++){
int left = j-1>=0?flag[j-1]:0;
int up = i-1>=0?flag[j]:0;
flag[j] = max(left, up)+in[i][j];
}
}
return flag[cols-1];
}
剑指：方法2
最长不含重复字符的子字符串
题目：请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。假设字符串中只包含从’a’到’z’的字符。例如，在字符串中”arabcacfr”，最长非重复子字符串为”acfr”，长度为4。
我的：不会
//动规：f（i）表示当前字符为结尾的最大子串长度
int test(string str) {
int length = str.size();
if(length<2) return length;
vector<int> flag(26,-1);
vector<int> result(length,0);
int ma = 0;
for(int i = 0 ;i < length;i++){
if(flag[str[i]-'a']<0){
flag[str[i]-'a']=i;
if(i>0)result[i] = result[i-1]+1;
else result[i]++;
}else{
int dif = i - flag[str[i]-'a'];
if(dif<= result[i-1]){
result[i] = dif;
}else{
result[i] = result[i-1]+1;
}
flag[str[i]-'a']=i;
}
ma = max(ma, result[i]);
}
return ma;
}
//方法2：双指针，左到右，start表示开始位置
int lengthOfLongestSubstring(string s) {
vector<int> dict(256, -1); // 用来记录字符上次出现的位置
int maxlen=0, start = -1;
for (int i = 0; i != s.length(); i++){
// s[i]字符上次出现的下标是否在start之后，若是，则重复了，则修改start为上一次s[i]的位置，从它后一位开始搜索
if (dict[s[i]] > start)
start = dict[s[i]];
dict[s[i]] = i;
maxlen = max(maxlen, i - start);
}
return maxlen;
}
剑指：
//动规：
int test(string str) {
int length = str.size();
if(length<2) return length;
vector<int> flag(26,-1);
int currentLength = 0;
int ma = 0;
for(int i = 0 ;i < length;i++){
if(flag[str[i]-'a']<0){
flag[str[i]-'a']=i;
currentLength++;
}else{
int dif = i - flag[str[i]-'a'];
if(dif <= currentLength){
currentLength = dif;
}else{
currentLength++;
}
flag[str[i]-'a']=i;
}
ma = max(ma, currentLength);
}
return ma;
}
N个骰子的点数
题目： 把n个骰子扔在地上，所有骰子朝上一面的点数之和为s，
输入n，打印出s的所有可能的值出现的概率。
n个骰子的总点数，最小为n，最大为6n，根据排列组合的知识，那个骰子，所有点数的排列数为6^n。
我们先统计每一个点数出现的次数，然后把每一个点数出现的次数除以6^n，就能求出每个点数出现的概率。
我的：
//递归：算出每个和的个数，5n个和
void dp( vector<int>& flag ,int nn, int n,int sum){
if(nn>n) {
flag[sum-n]++;
return;
}
for(int i = 1;i<7;i++){
sum += i;
dp(flag,nn+1,n,sum);
sum -= i;
}
}
vector<double> test(int n) {
vector<double> result;
if(n<1) return result;
vector<int > flag(5*n+1,0);
dp(flag, 1, n , 0);
for(int i : flag){
result.push_back(i/pow(6,n));
}
return result;
}
剑指：
思路一：
基于递归求骰子点数，时间效率不够高。
先把骰子分成两堆，第一堆只有一个，第二堆有n-1个，
单独的那一个可能出现1到6的点数，我们需要计算从1-6的每一种点数和剩下的n-1个骰子来计算点数和。
还是把n-1个那部分分成两堆，上一轮的单独骰子点数和这一轮的单独骰子点数相加，然后再和剩下的n-2个骰子来计算点数和。
不难发现这是一种递归的思路。
定义一个长度为6n-n+1的数组，和为s的点数出现的次数保存到数组的第s-n个元素里。
#include <iostream>
#include <cstdio>
using namespace std;
int g_maxValue = 6;
void Probability(int original, int current, int sum, int *pProbabilities)
{
if (current == 1)
{
pProbabilities[sum - original]++;
}
else
{
for (int i = 1; i <= g_maxValue; ++i)
{
Probability(original, current - 1, i + sum, pProbabilities);
}
}
}
void Probability(int number, int *pProbabilities)
{
for (int i = 1; i <= g_maxValue; ++i)
{
Probability(number, number, i, pProbabilities);
}
}
void PrintProbability(int number)
{
if (number < 1)
{
return;
}
int maxSum = number * g_maxValue;
int *pProbabilities = new int[maxSum - number + 1];
for (int i = number; i <= maxSum; ++i)
{
pProbabilities[i - number] = 0;
}
Probability(number, pProbabilities);
int total = pow( (double)g_maxValue, number);
for (int i = number; i <= maxSum; ++i)
{
double ratio = (double)pProbabilities[i - number] / total;
printf("%d: %e\n", i, ratio);
}
delete[] pProbabilities;
}
int main()
{
PrintProbability(6);
return 0;
}
思路二：
基于循环求骰子点数，时间性能好。
用两个数组来存储骰子点数的每一种出现的次数。
在一次循环中，第一个数组中的第n个数字表示骰子和为n出现的次数。
在下一次循环中我们加上一个新的骰子，此时和为n的骰子出现的次数应该等于上一次循环中骰子点数和为n-1、n-2、n-3、n-4、n-5与n-6的次数的综合，所以我们把另一个数组的第n个数字设为前一个数组对应的第n-1、n-2、n-3、n-4、n-5与n-6之和。
#include <iostream>
#include <cstdio>
using namespace std;
int g_maxValue = 6;
void PrintProbability(int number)
{
if (number < 1)
{
return ;
}
int *pProbabilities[2];
pProbabilities[0] = new int[g_maxValue * number + 1];
pProbabilities[1] = new int[g_maxValue * number + 1];
for (int i = 0; i < g_maxValue; ++i)
{
pProbabilities[0][i] = 0;
pProbabilities[1][i] = 0;
}
int flag = 0;
for (int i = 1; i <= g_maxValue; ++i)
{
pProbabilities[flag][i] = 1;
}
for (int k = 2; k <= number; ++k)
{
for (int i = 0; i < k; ++i)
{
pProbabilities[1 - flag][i] = 0;
}
for (int i = k; i <= g_maxValue * k; ++i)
{
pProbabilities[1 - flag][i] = 0;
for (int j = 1; j <= i && j <= g_maxValue; ++j)
{
pProbabilities[1 - flag][i] += pProbabilities[flag][i - j];
}
}
flag = 1 - flag;
}
double total = pow( (double)g_maxValue, number);
for (int i = number; i <= g_maxValue * number; ++i)
{
double ratio = (double)pProbabilities[flag][i] / total;
printf("%d: %e\n", i, ratio);
}
delete[] pProbabilities[0];
delete[] pProbabilities[1];
}
int main()
{
PrintProbability(6);
return 0;
}
股票的最大利润
题目：假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可获得的最大利润是多少？例如，一只股票在某些时间节点的价格为{9,11,8,5,7,12,16,14}。如果我们能在价格为5的时候买入并在价格为16时卖出，则能获得最大的利润为11.
我的：
//方法1：双指针
int test(vector<int> in) {
int length = in.size();
if(length<2) return 0;
int mi = in[0];
int ma = INT_MIN;
for(int i = 1;i<length;i++){
mi = min(mi,in[i]);
ma = max(ma, in[i] - mi);
}
return ma;
}
//方法2：动规，当前这个东西的最优解
int test(vector<int> in) {
int length = in.size();
if(length<2) return 0;
vector<int> flag(length,0);
int mi = in[0];
for(int i = 1;i<length;i++){
mi = min(mi,in[i]);
flag[i] = in[i]- mi>flag[i-1]?in[i]- mi:flag[i-1];
}
return flag[length-1];
}
剑指：方法1
背包问题
题目：
（1）经典的0-1背包问题（无物品的价值）：
假设有一个能装入容量为C的背包和n件重量分别为w1,w2,,...,wn的物品，能否从n件物品中挑选若干件恰好装满背包,要求找出所有满足上述条件的解。
当C=10,各件物品重量为{1,8,4,3,5,2}时，可以找到下列4组解：(1,4,3,2)、(1,4,5)、(8,2)和(3,5,2)。
我的：
//方法1：
void bag( vector<vector<int>>& result,vector<int> temp,int index, int sum ,int c, vector<int> in){
if(index>=in.size()){
if(sum==c) {
result.push_back(temp);
}
return;
}
if(sum+in[index]<=c){
temp.push_back(in[index]);
bag(result,temp,index+1, sum+in[index], c, in);
temp.pop_back();
}
bag(result,temp,index+1, sum, c, in);
}
vector<vector<int>> test(vector<int> in, int c) {
int length = in.size();
vector<vector<int>> result;
if(length<1) return result;
vector<int> temp;
bag(result,temp,0 , 0 , c,in);
return result;
}
（2）经典的0-1背包问题（有物品的价值）：
给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为C。应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？
我的:不对，不一定放满，用的是回溯？，不是动规，蛮力法求解0/1背包问题的时间复杂度为：2^n
int ma = 0;
void bag( vector<vector<int>>& result,vector<int> temp,int index, int sum ,int valsum ,int c, vector<int> in,vector<int> in2){
if(index>=in.size()){
if(sum==c) {
if(ma<valsum){
ma= valsum;
result.push_back(temp);
}
}
return;
}
if(sum+in[index]<=c){
temp.push_back(in[index]);
bag(result,temp,index+1, sum+in[index],valsum+in2[index], c, in,in2);
temp.pop_back();
}
bag(result,temp,index+1, sum,valsum, c, in, in2);
}
vector<vector<int>> test(vector<int> in, vector<int> in2,int c) {
int length = in.size();
vector<vector<int>> result;
if(length<1) return result;
vector<int> temp;
bag(result,temp,0 , 0 ,0, c,in,in2);
return result;
}
动规：
image.png
int test(vector<int> zhong, vector<int> value,int n, int c) {
int length = zhong.size();
if(length<1) return 0;
vector<vector<int>> flag(n+1 ,vector<int>(c+1));
for(int i = 1;i<=n;i++){
for(int j = 1;j<=c;j++){
if(zhong[i-1]>j) flag[i][j] = flag[i-1][j];
else{
flag[i][j] = max(flag[i-1][j],flag[i-1][j-zhong[i-1]]+value[i-1]);
}
}
}
for(int i = n,j = C; i > 0; i--){ //找出放入的物品
if(V[i][j] > V[i-1][j]){
x[i-1] = 1;
j = j - a[i-1].wight;
}
else
x[i-1] = 0;
return flag[n][c];
}
236. Lowest Common Ancestor of a Binary Tree
题目：
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]
image
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Note:
- All of the nodes' values will be unique.
- p and q are different and both values will exist in the binary tree.
bool dfs(TreeNode* root,TreeNode* p, vector<TreeNode*>& temp){
temp.push_back(root);
if(root == p) return true;
if(root->left!=NULL) {
if(dfs(root->left, p, temp)) return true;
temp.pop_back();
}
if(root->right!=NULL){
if(dfs(root->right, p, temp)) return true;
temp.pop_back();
}
return false;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==NULL||p==NULL||q==NULL) return NULL;
vector<TreeNode*> temp1;
vector<TreeNode*> temp2;
if(dfs(root, p, temp1)&&dfs(root, q, temp2)){
for(int i = 0;i<temp1.size()&&i<temp2.size();i++){
if(temp1[i]!=temp2[i]){
return temp1[i-1];
}
if(temp1[i]==p){
return temp1[i];
}
if(temp2[i]==q){
return temp2[i];
}
}
}
return NULL;
}
网友评论