二叉树中和为某一值的路径
输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。
从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
保证树中结点值均不小于 0
。
数据范围
树中结点的数量 [0,1000]
。
样例
给出二叉树如下所示,并给出num=22。
5
/ \
4 6
/ / \
12 13 6
/ \ / \
9 1 5 1
输出:[[5,4,12,1],[5,6,6,5]]
sum不用回溯
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> ans;
vector<int>path;
vector<vector<int>> findPath(TreeNode* root, int sum) {
dfs(root,sum);
return ans;
}
void dfs(TreeNode *root,int sum)
{
if(!root) return ;//到空节点直接return
path.push_back(root->val);
sum-=root->val;
//为叶子结点且和为sum,保存路径
if(!root->left&&!root->right&&!sum) ans.push_back(path);
dfs(root->left,sum);
dfs(root->right,sum);
path.pop_back();//回溯,sum不用回溯因为每个dfs都有sum
}
};
回溯sum
class Solution {
public:
vector<vector<int>> ans;
vector<int>path;
int s;
vector<vector<int>> findPath(TreeNode* root, int sum) {
s=sum;//用全局变量存sum
dfs(root);
return ans;
}
void dfs(TreeNode *root)
{
if(!root) return ;//到空节点直接return
path.push_back(root->val);
s-=root->val;
//为叶子结点且和为sum,保存路径
if(!root->left&&!root->right&&!s) ans.push_back(path);
dfs(root->left);
dfs(root->right);
path.pop_back();//回溯
s+=root->val;//s回溯
}
};
打印路径
class Solution {
public:
vector<vector<int>> ans;
vector<int>path;
int s;
vector<vector<int>> findPath(TreeNode* root, int sum) {
dfs(root);
return ans;
}
void dfs(TreeNode *root)
{
if(!root) return ;//到空节点直接return
path.push_back(root->val);
//为叶子结点,保存路径
if(!root->left&&!root->right) ans.push_back(path);
dfs(root->left);
dfs(root->right);
path.pop_back();//回溯
}
};
n皇后问题对行dfs
#include <iostream>
using namespace std;
const int N = 20;
// bool数组用来判断搜索的下一个位置是否可行
// col列,dg对角线,udg反对角线
// g[N][N]用来存路径
int n;
char g[N][N];
bool col[N], dg[N], udg[N];
void dfs(int u) {
// u == n 表示已经搜了n行,故输出这条路径
if (u == n) {
for (int i = 0; i < n; i ++ ) puts(g[i]); // 等价于cout << g[i] << endl;
puts(""); // 换行
return;
}
//对n个位置按行搜索
for (int i = 0; i < n; i ++ )
// 剪枝(对于不满足要求的点,不再继续往下搜索)
// udg[n - u + i],+n是为了保证下标非负
if (!col[i] && !dg[u + i] && !udg[n - u + i]) {
g[u][i] = 'Q';
col[i] = dg[u + i] = udg[n - u + i] = true;
dfs(u + 1);
col[i] = dg[u + i] = udg[n - u + i] = false; // 恢复现场 这步很关键
g[u][i] = '.';
}
}
int main()
{
cin>>n;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
g[i][j] = '.';
dfs(0);
return 0;
}
数字全排列
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 10;
int n;
int path[N]; // 从0到n-1共n个位置 存放一个排列
bool state[N]; // 存放每个数字的使用状态 true表示使用了 false表示没使用过
void dfs(int u)
{
if (u == n) // 一个排列填充完成
{
for (int i = 0; i < n; i ++) printf("%d ",path[i]); // 注意格式 别忘了每两个数字间用空格隔开
puts(""); // 相当于输出一个回车
return;
}
for (int i = 1; i <= n; i ++)
{
if (!state[i])
{
path[u] = i; // 把 i 填入数字排列的位置上
state[i] = true; // 表示该数字用过了 不能再用
dfs(u + 1); // 这个位置的数填好 递归到右面一个位置
state[i] = false; // 恢复现场 该数字后续可用
}
}
// for 循环全部结束了 dfs(u)才全部完成 回溯
}
int main()
{
scanf("%d", &n);
dfs(0); // 在path[0]处开始填数
return 0;
}
树的重心
#include<bits/stdc++.h>
using namespace std;
const int N=1e7,M=2*N;
int h[N],e[M],ne[M],idx;
int n;
bool st[N];
int ans=N;//最大值的最小值
void add(int a,int b)
{
e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
int dfs(int u)//以u为根的树的点的数量
{
st[u]=true;
int sum=1,res=0;//sum当前树节点个数,res为此点删掉后每一个联通块的点数的最大值
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(!st[j])
{
int s=dfs(j);//当前子树大小
res=max(res,s);
sum+=s;//以j为根结点的子树是以u为根结点的子树的一部分
}
}
res=max(n-sum,res);//u节点上面的一坨
ans=min(ans,res);
return sum;
}
int main()
{
cin>>n;
memset(h,-1,sizeof h);
for (int i = 0; i < n - 1; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
dfs(1);
cout<<ans<<endl;
return 0;
}
t到s的简单路径
void dfs(int t)//从t到s的所有简单路径
{
st[t]=1;
if(s==t)
{//到s点了输出
for(int i=1;i<cnt;i++) cout<<path[i];
}
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
if(!st[j])
{
st[j]=1;
path[++cnt]=j;
dfs(j);
st[j]=0;
cnt--;
}
}
}