一：分治算法
「 divide and conquer」，全称分而治之，是一种非常重要且常见的算法策略。
分治通常基于递归实现，包括“分”和“治”两个步骤。
- 分（划分阶段）：递归地将原问题分解为两个或多个子问题，直至到达最小子问题时终止。
- 治（合并阶段）：从已知解的最小子问题开始，从底至顶地将子问题的解进行合并，构建出原问题的解。
如何判断分治问题
一个问题是否可以使用分治解决的几个判断依据：
-
问题可以被分解
原问题可以被分解成规模更小、类似的子问题，以及能够以相同方式递归地进行划分。
-
子问题是独立的
子问题之间是没有重叠的，互相没有依赖，可以被独立解决。
-
子问题的解可以被合并
原问题的解通过合并子问题的解得来。
分治法的过程——一分二治三合并
分：递归或迭代地将原问题分解为各个的子问题(性质相同的、相互独立的子问题)
治：若子问题规模足够小则直接解决，否则递归解决各子问题
合并：逐层合并各子问题的解得到原问题的解
关键点：
原问题和各个子问题都是同类的重复子问题—满足递归的定义
除了向下递归问题还要向上合并结果
通过分治可以提高效率
分治不仅可以有效地解决算法问题，往往还可以带来算法效率的提升。
在排序算法中，快速排序、归并排序、堆排序相较于选择、冒泡、插入排序更快，就是因为它们应用了分治策略。
归并排序
void mergeSort(int a[],int l,int r){
/*递归结束条件*/
if(l==r) return;//当前只有一个元素
int mid = (l + r) / 2;
/*分治*/
//[l,..,r]分成[l,..,mid];[mid+1,...,r]
mergeSort(a, 0, mid);
mergeSort(a, mid + 1, r);
/*合并结果*/
//[l,..,mid]和[mid+1,r]进行排序
//用辅助数组aux存储排序结果，然后赋值给原数组a
int *aux = new int[r - l + 1];
int i = l, j = mid + 1;
int k = 0;//aux指向
while(i<=mid && j<=r){
if(a[i]<=a[j]){
aux[k++] = a[i++];
}else{
aux[k++] = a[j++];
}
}
//分析谁在范围内
while(i<=mid){
aux[k++] = a[i++];
}
while(j<=r){
aux[k++] = a[j++];
}
//把aux[0,..,r-l+1]这段范围赋值给a[l,...r]
for (int t = l; t <=r ;t++){
a[t] = aux[t - l];
}
}
分治三大步骤：
- 递归结束条件
- 进行分治，自顶向下
- 合并结果，自底向上
也可以把合并结果单独写成函数
void _mergeHelper(int a[], int l, int mid, int r){
int *aux = new int[r - l + 1];
// 对[l,..,mid]和[mid+1,..,r]进行排序
int i = l, j = mid + 1;
for(int k=0;k<=r-l+1;k++){//r-l+1取等
if(i>mid){
aux[k]=a[j++];
}
else if(j>r){
aux[k]=a[i++];
}
else if(a[i]>a[j]){
aux[k]=a[j++];
}
else{
aux[k]=a[i++];
}
}
//赋值
for (int t = l; t <= r; t++){
// a中[l,r]对应aux是[0,r-l+1]
a[t] = aux[t - l];
}
}
void mergeSort(int a[], int l, int r)
{
/*递归结束条件*/
if (l == r)
return; // 当前只有一个元素
int mid = (l + r) / 2;
/*分治*/
//[l,..,r]分成[l,..,mid];[mid+1,...,r]
mergeSort(a, 0, mid);
mergeSort(a, mid + 1, r);
/*合并结果*/
_mergeHelper(a, l, mid, r);
}
对应for中，也就是：
条件1：i<=mid
条件2: j<=r
- 条件一不满足
- 条件二不满足
- 条件一二都满足，比较大小
for (int k = 0; k <= r - l + 1; k++){ // r-l+1取等 if (i <= mid && j <= r){ //比较必须都在范围 if (a[i] > a[j]){ aux[k] = a[j++]; } else{ aux[k] = a[i++]; } } //一端越界，只复制另一端 else if (i>mid){ aux[k] = a[j++]; } else {//j>r aux[k] = a[i++]; } }
力扣22
22. 括号生成
分治做法
思路：(a)b
(
a
)
b
，
n
u
m
s
(
a
)
表示
a
生成的括号个数
\left( a \right) b\text{，}nums\left( a \right) \text{表示}a\text{生成的括号个数}
(a)b，nums(a)表示a生成的括号个数
n = 2 n=2 n=2
n u m s ( a ) = 1 , n u m s ( b ) = 0 结果： ( ( ) ) nums\left( a \right) =1,nums\left( b \right) =0\ \text{结果：}\left( \left( \right) \right) nums(a)=1,nums(b)=0 结果：(())
n u m s ( a ) = 0 , n u m s ( b ) = 1 结果： ( ) ( ) nums\left( a \right) =0,nums\left( b \right) =1\ \text{结果：}\left( \right) \left( \right) nums(a)=0,nums(b)=1 结果：()()
n = 3 n=3 n=3
n u m s ( a ) = 2 , n u m s ( b ) = 0 结果： ( ( ) ( ) ) 或 ( ( ( ) ) ) nums\left( a \right) =2,nums\left( b \right) =0\ \text{结果：}\left( \left( \right) \left( \right) \right) \ \text{或}\left( \left( \left( \right) \right) \right) nums(a)=2,nums(b)=0 结果：(()()) 或((()))
n u m s ( a ) = 1 , n u m s ( b ) = 1 结果： ( ( ) ) ( ) nums\left( a \right) =1,nums\left( b \right) =1\,\,\text{结果：}\left( \left( \right) \right) \left( \right) nums(a)=1,nums(b)=1结果：(())()
n u m s ( a ) = 0 , n u m s ( b ) = 2 结果： ( ) ( ) ( ) 或 ( ) ( ( ) ) nums\left( a \right) =0,nums\left( b \right) =2\,\,\text{结果：}\left( \right) \left( \right) \left( \right) \text{或}\left( \right) \left( \left( \right) \right) nums(a)=0,nums(b)=2结果：()()()或()(())
vector<string> generateParenthesis(int n) {
vector<string> res;
//递归结束，底部
if(n==0) return {""};
//(a)b
for(int i=1;i<=n;i++){
//分治
vector<string> aa=generateParenthesis(i-1);
vector<string> bb=generateParenthesis(n-i);
//向上合并aa与bb的结果
//乘法原理，每一个aa和每一个bb组合
for(auto m:aa){//m是aa的一个
for(auto n:bb){//n是bb的一个
res.push_back("("+m+")"+n);
}
}
}
return res;
}
回溯做法
先回溯后选元素，所以不符合条件不进行回溯
class Solution {
public:
vector<string> generateParenthesis(int n) {
string str;
this->n=n;
findpar(str, 0, 0);
return res;
}
private:
vector<string> res;
int n;
void findpar(string str, int l, int r) {
/*右括号数量必须少于等于左括号*/
if (l == n && r == n) {
res.push_back(str);
return;
}
str += "(";
//生成左括号条件
if (l < n) {
findpar(str, l + 1, r);
}
str.pop_back();//去掉该选择
str += ")";
//生成右括号条件
if (r < l) {
findpar(str, l, r + 1);
}
}
};
或者选用声明两个变量，无需pop_back()
void findpar(string str, int l, int r) {
/*右括号数量必须少于等于左括号*/
if (l == n && r == n) {
res.push_back(str);
return;
}
string s1=str+"(";
string s2=str+")";
//生成左括号条件
if (l < n) {
findpar(s1, l + 1, r);
}
//生成右括号条件
if (r < l) {
findpar(s2, l, r + 1);
}
}
// 生成左括号条件
if (l < n) {
findpar(str + "(", l + 1, r);
}
// 生成右括号条件
if (r < l) {
findpar(str + ")", l, r + 1);
}
也可以采用先选元素再回溯的策略，不过要加候选项
class Solution {
public:
vector<string> generateParenthesis(int n) {
this->n = n;
string str;
findPar(str, 0, 0);
return res;
}
private:
int n;
string data = "()"; // 供选
vector<string> res;
void findPar(string str, int l, int r) {
/*不满足条件结束---剪枝*/
if (l > n || r > l) {
return;
}
/*满足条件记录结果*/
if (l == n && r == n) {
res.push_back(str);
return;
}
for (int i = 0; i < data.size(); i++) {
/*加元素统计l,r*/
if (data[i] == '(')
l++;
else
r++;
/*先加再回溯*/
str += data[i];
findPar(str, l, r);
str.pop_back();
/*去元素统计l,r*/
if (data[i] == '(')
l--;
else
r--;
}
}
};
for (int i = 0; i < data.size(); i++):中：data="()"就是候选项
注意不符合条件的要剪枝，就是提前return;
力扣169
169. 多数元素
类似归并排序，首先每次对半分数组，直至只剩自己
但是在合并结果时候需要考虑：这里是求出现最多的
需要记录左边出现最多的和右边出现最多的，返回出现最多的那个值即可
class Solution {
public:
int majorityElement(vector<int>& nums) {
return findMajor(nums,0,nums.size()-1);
}
private:
/*利用分治，分别求左右两个区间的众数*/
int findMajor(vector<int>& nums,int l,int r){
if(l==r) return nums[l];//递归结束
int mid=(l+r)/2;
/*分治*/
int left=findMajor(nums,l,mid);
int right=findMajor(nums,mid+1,r);
/*合并结果*/
//记录频次
if(left==right) return left;
int col1=0,col2=0;
for(int i=l;i<=r;i++){
if(nums[i]==left) col1++;
if(nums[i]==right) col2++;
}
return (col1>col2)?left:right;
}
};
也可以利用map统计频次，针对这道题更简单
int majorityElement(vector<int>& nums) {
unordered_map<int,int> mp;
for(auto &val:nums){
if(mp.find(val)!=mp.end()){
mp[val]++;
}else{
mp[val]=1;
}
//输出
if(mp[val]>nums.size()/2){
return val;
}
}
return -1;
}
二：树
父节点，兄弟节点，子树
满二叉树：
-
一个二叉树所有的非叶子节点都存在左右两个孩子
-
并且所有叶子节点都在同一层级上
这样的树被称为满二叉树
完全二叉树：
-
从根往下数，除了最下层外都是全满（都有两个子节点）
-
而且最下层所有叶结点都
向左边靠拢填满。
这样定义是为了从根依次向下，按照从左至右的顺序标号后可以快速计算出给定节点的孩子和双亲节点
根节点编号为0：
- 对于i>0，其父节点的编号为*(i-1)/2*
- 若2·i+1<n，其
左子节点的序号为2·i+1，否则没有左子节点 - 若2·i+2<n，其
右子节点的序号为2·i+2，否则没有右子节点
完全二叉树可以用数组存储，编号就可以求出父节点和子节点的，可以表明树关系
树的遍历
dfs和bfs
用递归方法求层次遍历
- 选用先序遍历，先访问节点，在依次访问左子树和右子树
- 关键在于输出，需要维护一个当前节点所在层level的信息
- 用for遍历每一层节点，当level在该层后，就进行输出
首先创建好二叉树
struct TreeNode
{
int val;
TreeNode *left, *right;
TreeNode(int x, TreeNode *left = NULL, TreeNode *right = NULL) : val(x), left(left),\ right(right) {}
};
TreeNode* createTree(){
/* 30
20 40
70 80 50 100
*/
TreeNode *a = new TreeNode(70);
TreeNode *b = new TreeNode(80);
TreeNode *c = new TreeNode(50);
TreeNode *d = new TreeNode(100);
TreeNode *e = new TreeNode(20, a, b);
TreeNode *f = new TreeNode(40, c, d);
TreeNode *g = new TreeNode(30, e, f);
return g;
}
求二叉树深度函数
int depth(TreeNode* root){
if(root==NULL)
return 0;
return max(depth(root->left), depth(root->right)) + 1;
}
递归层次遍历–不分层
void _dfs(TreeNode* root,int level){
if(!root)//左右孩子不存在情况
return;
if(level==1){//只输出该层节点
cout << root->val << " ";
return;
}
_dfs(root->left, level - 1);
_dfs(root->right, level - 1);
}
void levelTraverse(TreeNode* root){
if(root==NULL)
return;
int dep = depth(root);//求出树深度
//对每一层做好标记，从根节点1开始
for (int i = 1; i <= dep;i++){
_dfs(root, i);
// cout<<endl;//分层
}
}
同理N叉数的层次遍历
429. N 叉树的层序遍历
递归：
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
dfs(root,0);
return res;
}
private:
vector<vector<int>> res;
void dfs(Node* root,int level){
if(root==NULL) return;
if(level==res.size()){
res.push_back({});
}
//存结点
res[level].push_back(root->val);
//递归
for(auto& x:root->children){
dfs(x,level+1);
}
}
};
非递归：
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> res;
if(root==NULL) return res;
using pr=pair<Node*,int>;
queue<pr> que;
que.push(make_pair(root,0));
while(!que.empty()){
auto [tmp,level]=que.front();
que.pop();
if(level==res.size()){
res.push_back({});
}
res[level].push_back(tmp->val);
for(auto& x:tmp->children){
que.push(make_pair(x,level+1));
}
}
return res;
}
二叉树中序
94. 二叉树的中序遍历
细节：一定要把结果作为全局变量，或者引用参数传递
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
if(root==NULL) return {};
//左根右
inorderTraversal(root->left);
res.push_back(root->val);
inorderTraversal(root->right);
return res;
}
private:
vector<int> res;//结果
};
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
dfs(root,res);
return res;
}
private:
void dfs(TreeNode *root,vector<int>& ans){//必须传引用
if(root==NULL) return;
dfs(root->left,ans);
ans.push_back(root->val);
dfs(root->right,ans);
}
};
或者结果作为私用变量，另写一个void类型的dfs
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
dfs(root);
return ans;
}
private:
vector<int> ans;
void dfs(TreeNode *root){//必须传引用
if(root==NULL) return;
dfs(root->left);
ans.push_back(root->val);
dfs(root->right);
}
};
二叉树层次遍历，区分出层次
102. 二叉树的层序遍历
关键在于：如何分层
循环前，当前队列里的元素均在同一层
然后依次访问节点，自己出队，把其左右孩子放入队列
用变量记录队列元素作为循环结束标志
vector<vector<int>> levelOrder(TreeNode* root) {
if(root==NULL) return {};
vector<vector<int>> res;
//定义队列
queue<TreeNode*> que;
//根节点入队
que.push(root);
//遍历
while(!que.empty()){
int cursize=que.size();
vector<int> ans;
for(int i=0;i<cursize;i++){
TreeNode* tmp=que.front();
que.pop();//别忘了出队
ans.push_back(tmp->val);
//左右孩子入队
if(tmp->left) que.push(tmp->left);
if(tmp->right) que.push(tmp->right);
}
res.push_back(ans);
}
return res;
}
也可以格外定义level变量，表示层数。
res[level]就是要存放的变量，然后为了保证访问合法性，需要进行判断
vector<vector<int>> levelOrder(TreeNode* root) {
using pr=pair<TreeNode*,int>;
if(root==NULL) return {};
vector<vector<int>> res;
//定义队列
queue<pr> que;
que.push(make_pair(root,0));
//遍历
while(!que.empty()){
auto [tmp,level]=que.front();
que.pop();
//访问合法性检查
if(level>=res.size()){
res.push_back({});
}
res[level].push_back(tmp->val);
//左右节点入队
if(tmp->left) que.push(make_pair(tmp->left,level+1));
if(tmp->right) que.push(make_pair(tmp->right,level+1));
}
return res;
}
还可以用先序遍历来递归
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
dfs(root,0);
return res;
}
private:
vector<vector<int>> res;
void dfs(TreeNode* root,int level){
if(root==NULL) return;
if(level==res.size()){
res.push_back(vector<int>());//{}也可以
}
//先加入节点
res[level].push_back(root->val);
//递归
dfs(root->left,level+1);
dfs(root->right,level+1);
}
};
多叉树先序
589. N 叉树的前序遍历
N插数的数据结构，孩子结点用vector数组存放
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
本题由于数据：进行序列化表示，所以孩子结点之间存在顺序
方法一：栈非递归实现
由于是先序遍历，先访问结点，再加入孩子。
注意栈的后进先出特性，这里孩子顺序从右至左进入栈
vector<int> preorder(Node* root) {
vector<int> res;
if(root==NULL) return res;
stack<Node*> sta;
sta.push(root);
while(!sta.empty()){
Node* tmp=sta.top();
sta.pop();
res.push_back(tmp->val);
//注意倒着放孩子
auto it=tmp->children.rbegin();
for(;it!=tmp->children.rend();it++){
sta.push(*it);//*it就是tmp->children
}
}
return res;
}
方法二：递归实现
class Solution {
public:
vector<int> preorder(Node* root) {
if(root==NULL) return res;
res.push_back(root->val);
//对孩子结点进行递归
for(auto& x:root->children){
preorder(x);
}
return res;
}
private:
vector<int> res;
};
先序和中序遍历创建树
105. 从前序与中序遍历序列构造二叉树
先序可以确定根节点，中序可以划分左右子树
- 然后依据中序的左右子树的个数，把先序的左右划分两部分
- 然后左右两部分的先序又可以确定出根结点，以此类推
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
this->pre=preorder;
this->in=inorder;
int s1=pre.size();
int s2=in.size();
return _build(0,s1-1,0,s2-1);
}
private:
vector<int> pre;
vector<int> in;
//pre[l1,r1] in[l2,r2]
TreeNode* _build(int l1,int r1,int l2,int r2){
//递归结束
if(l1>r1) return NULL;//先序是结束标志
//生成根节点
TreeNode* root=new TreeNode(pre[l1]);
//去中序找root->val
int mid=l2;
while(in[mid]!=root->val) mid++;
//递归左右两部分 中序：[l2,mid-1] [mid+1,r2]
int leftsize=mid-l2;
//先序 [l1+1,x] x-l1=leftsize [x+1,r1]
root->left=_build(l1+1,l1+leftsize,l2,mid-1);
root->right=_build(l1+leftsize+1,r1,mid+1,r2);
return root;
}
};
当然先序左右两部分下标还可以依据rightsize来推断
//中序：[l2,mid-1] [mid+1,r2] int leftsize=mid-l2; //先序 [l1+1,x] x-l1=leftsize [x+1,r1] int rightsize=r2-mid; //先序 [x,r1] r1-x+1=rightsize即：x=r1-rightsize+1 root->left=_build(l1+1,l1+leftsize,l2,mid-1); root->right=_build(r1-rightsize+1,r1,mid+1,r2);
也可以传入指针的引用，函数返回值为void
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
this->pre=preorder;
this->in=inorder;
int s1=pre.size();
int s2=in.size();
TreeNode* mm;
_build(mm,0,s1-1,0,s2-1);
return mm;
}
private:
vector<int> pre;
vector<int> in;
//pre[l1,r1] in[l2,r2]
void _build(TreeNode*& root,int l1,int r1,int l2,int r2){
//递归结束
if(l1>r1) return;//先序是结束标志
//生成根节点
root=new TreeNode(pre[l1]);
//去中序找root->val
int mid=l2;
while(in[mid]!=root->val) mid++;
//递归左右两部分 中序：[l2,mid-1] [mid+1,r2]
int leftsize=mid-l2;
//先序 [l1+1,x] x-l1=leftsize [x+1,r1]
int rightsize=r2-mid;
//先序 [x,r1] r1-x+1=rightsize即：x=r1-rightsize+1
_build(root->left,l1+1,l1+leftsize,l2,mid-1);
_build(root->right,r1-rightsize+1,r1,mid+1,r2);
}
};
二叉树查找值为x的结点
分治思想，先找左子树，找不到再去找右子树
TreeNode* findNode(TreeNode* root,int x){
if(root==NULL) return NULL;
if(root->val==x)
return root;//找到了
//先去左子树找，找不到去右子树找
TreeNode *leftSide = findNode(root->left, x);
TreeNode *rightSide = findNode(root->right, x);
if(leftSide){
return leftSide;
}
else{//rightSide
return rightSide;
}
}
//先去左子树找，找不到去右子树找
return
findNode(root->left, x)?findNode(root->left, x):findNode(root->right, x);
也可以简写成一句话
return findNode(root->left,x)?findNode(root->left,x):findNode(root->right,x);
求堂兄弟节点
993. 二叉树的堂兄弟节点
这道题说白了就是两个子问题的集合
- 求两个结点的父节点
- 求两个结点的自身深度
如何求父节点
递归
区别就在于判断的是当前结点的孩子结点是否为x，避免NULL->val，需要先判断存在
TreeNode* findParent(TreeNode* root,int x){
if(root==NULL) return NULL;
//左右子树存在且值为x则找到父节点
if(root->left){
if(root->left->val==x) return root;
}
if(root->right){
if(root->right->val==x) return root;
}
if(findParent(root->left,x)){
return findParent(root->left,x);
}else{
return findParent(root->right,x);
}
}
层次遍历求
//层次遍历
TreeNode* findParent(TreeNode* root,int x){
if(root==NULL) return NULL;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
TreeNode* tmp=que.front();
que.pop();
if(tmp->left){
//判断左孩子值
if(tmp->left->val==x){
return tmp;
}
que.push(tmp->left);
}
if(tmp->right){
//判断右孩子值
if(tmp->right->val==x){
return tmp;
}
que.push(tmp->right);
}
}
return NULL;
}
栈的先序遍历求
//先序遍历
TreeNode* findParent(TreeNode* root,int x){
if(root==NULL) return NULL;
stack<TreeNode*> sta;
sta.push(root);
while(!sta.empty()){
TreeNode* tmp=sta.top();
sta.pop();
//栈后进先出，所以先右后左
if(tmp->right){
if(tmp->right->val==x){
return tmp;
}
sta.push(tmp->right);
}
if(tmp->left){
if(tmp->left->val==x){
return tmp;
}
sta.push(tmp->left);
}
}
return NULL;
}
如何求深度
递归
int nodeLevel(TreeNode* root,int x,int level){
if(root==NULL) return -1;//表示不存在
if(root->val==x) return level;
int l=nodeLevel(root->left,x,level+1);
int r=nodeLevel(root->right,x,level+1);
if(l!=-1){
return l;
}
if(r!=-1){
return r;
}
return -1;
}
非递归
int nodeLevel(TreeNode* root,int x){
if(root==NULL) return -1;
using pr=pair<TreeNode*,int>;
queue<pr> que;
que.push(make_pair(root,1));
while(!que.empty()){
auto[node,level]=que.front();
que.pop();
//当前值满足条件
if(node->val==x) return level;
if(node->left){
que.push(make_pair(node->left,level+1));
}
if(node->right){
que.push(make_pair(node->right,level+1));
}
}
return -1;
}
如果queue不放pair对
int nodeLevel(TreeNode* root, int x) {
if (root == NULL)
return -1;
queue<TreeNode*> que;
que.push(root);
int level = 0;
while (!que.empty()) {
int curSize = que.size();
level++;//层加一
for (int i = 0; i < curSize; i++) {
TreeNode* node = que.front();
que.pop();
// 当前值满足条件
if (node->val == x)
return level;
if (node->left) {
que.push(node->left);
}
if (node->right) {
que.push(node->right);
}
}
}
return -1;
}
本题解法
可以合并一个程序，由于返回结点和深度，所以用私有变量记录，然后函数返回值为void
class Solution {
public:
bool isCousins(TreeNode* root, int x, int y) {
lx = ly = 0;
tx = NULL;
ty = NULL;
find(root, NULL, x, y, 1);
//不存在父节点
if (!tx || !ty)
return false;
//父节点不同，但深度相同
if (tx != ty && lx == ly)
return true;
else
return false;
}
private:
TreeNode *tx, *ty;
int lx, ly;
void find(TreeNode* root, TreeNode* par, int x, int y, int level) {
if (root == NULL)
return;
if (root->val == x) {
lx = level;
tx = par;
}
if (root->val == y) {
ly = level;
ty = par;
}
find(root->left, root, x, y, level + 1);
find(root->right, root, x, y, level + 1);
}
};
提前判断再递归也可以
if(root->left){ find(root->left, root, x, y, level + 1); } if(root->right){ find(root->right, root, x, y, level + 1); }
当然也可以用pair对返回深度和父节点，然后调用两次
class Solution {
public:
bool isCousins(TreeNode* root, int x, int y) {
pr.first = NULL;
pr.second = 0;
auto [k1, v1] = find(root, NULL, x, 1);
auto [k2, v2] = find(root, NULL, y, 1);
if(k1!=k2 && v1==v2) return true;
else return false;
}
private:
pair<TreeNode*, int> pr;
pair<TreeNode*, int> find(TreeNode* root, TreeNode* par, int v, int level) {
if (root == NULL)
return pr;
if (root->val == v) {
//pr.first = par;
//pr.second = level;
//pr=make_pair(par,level);
pr={par,level};
return pr;
}
find(root->left, root, v, level + 1);
find(root->right, root, v, level + 1);
return pr;
}
};
pair的赋值
pair<> =make_pair();
pair<>={};
pair<> fisrst,second单独赋值
求最近公共祖先
236. 二叉树的最近公共祖先
解法一：利用map记录二叉树的所有结点的父节点（该题无重复元素），然后把其中一个结点的路径用set记录下来，那么遍历另一个节点时，只要相遇(就是该节点第一次遍历到上一个结点走过的，也就是set记录过)，则该点就是所求点。
比如对于5：5的父节点是9，9的父节点是7，组成路径：597
向上找父节点时，只要遇到红色结点就是所求。
比如：3第一次遇到是7，则：3和6的最近公共子结点是7
求所有结点父节点
一定要：mp【节点值】=父节点，因为这样mp[mp[x]->val]可以不断求父节点
//mp[结点]=深度
unordered_map<int,TreeNode* > mp;
void findParent(TreeNode* root){
if(root==NULL) return;
//mp[结点值]=父节点指针
if(root->left){
mp[root->left->val]=root;
}
if(root->right){
mp[root->right->val]=root;
}
findParent(root->left);
findParent(root->right);
}
输出结果：
findParent(root); for(auto& [k,v]:mp){ cout<<k<<"的父节点是"<<v->val<<endl; }
cout<< mp[11]->val<<endl;//5
cout<<mp[mp[11]->val]->val<<endl;//2
cout<< mp[mp[mp[11]->val]->val]->val<<endl;//1
同样可以求深度
//mp[结点]=深度
unordered_map<TreeNode* ,int> mp;
void findlevel(TreeNode* root,int level){
if(root==NULL) return;
mp[root]=level;
findlevel(root->left,level+1);
findlevel(root->right,level+1);
}
本题解法
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
findFather(root);
// 从p开始，将其所有父节点存入set中
set<int> st;
//st.insert(root->val);
while (p) {
st.insert(p->val);
p = mp[p->val];
}
// 从q开始，查找set第一个存在的
while (q) {
if(st.count(q->val)){
return q;
}
q=mp[q->val];
}
return NULL;
}
private:
// mp[节点值]=父节点
unordered_map<int, TreeNode*> mp;
void findFather(TreeNode* root) {
if (root == NULL)
return;
if (root->left) {
mp[root->left->val] = root;
findFather(root->left);
}
if (root->right) {
mp[root->right->val] = root;
findFather(root->right);
}
}
};
// 从q开始，查找set第一个存在的 while (q) { if(st.count(q->val)){ return q; } q=mp[q->val]; }可以改写
// 从q开始，查找set第一个存在的 while (!st.count(q->val)) { q = mp[q->val]; } return q;加入路径也可以依据值：
set<int> st; st.insert(root->val); while (p->val!=root->val) { st.insert(p->val); p = mp[p->val]; }
![[数据集][目标检测]零售柜零食检测数据集VOC+YOLO格式5422张113类](https://img-blog.csdnimg.cn/direct/7a4d2cc4bc99494182c1537f7f797699.png)
