1.自顶向下
从某一个节点(不一定是根节点)，从上向下寻找路径，到某一个节点(不一定是叶节点)结束
继续细分的话还可以分成一般路径与给定和的路径
[257 二叉树所有路径] （https://leetcode-cn.com/problems/binary-tree-paths/）
[面试题 求和路径]（https://leetcode-cn.com/problems/paths-with-sum-lcci/）
[112路径总和]（https://leetcode-cn.com/problems/path-sum/）
[113路径总和II]（https://leetcode-cn.com/problems/path-sum-ii/）
[437路径总和III]（https://leetcode-cn.com/problems/path-sum-iii/）
[988]从叶节点开始的最小字符串（https://leetcode-cn.com/problems/smallest-string-starting-from-leaf/）
2.非自顶向下
就是从任意节点到任意节点的路径，不需要自顶向下
[124 二叉树中最大路径和]（https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/）
[687最长同值路径]（https://leetcode-cn.com/problems/longest-univalue-path/）
[543二叉树直径]（https://leetcode-cn.com/problems/diameter-of-binary-tree/）
解题模板 DFS
- 1.自顶向下
1、如果是找路径和等于给定target的路径的，那么可以不用新增一个临时变量cursum来判断当前路径和，
只需要用给定和target减去节点值，最终结束条件判断target==0即可
2、是否要回溯：二叉树的问题大部分是不需要回溯的，原因如下：
二叉树的递归部分：dfs(root->left),dfs(root->right)已经把可能的路径穷尽了,
因此到任意叶节点的路径只可能有一条，绝对不可能出现另外的路径也到这个满足条件的叶节点的;
而对比二维数组(例如迷宫问题)的DFS,for循环向四个方向查找每次只能朝向一个方向，并没有穷尽路径，
因此某一个满足条件的点可能是有多条路径到该点的并且visited数组标记已经走过的路径是会受到另外路径是否访问的影响，这时候必须回溯
3、找到路径后是否要return:
取决于题目是否要求找到叶节点满足条件的路径,如果必须到叶节点,那么就要return;
但如果是到任意节点都可以，那么必不能return,因为这条路径下面还可能有更深的路径满足条件，还要在此基础上继续递归
4、是否要双重递归(即调用根节点的dfs函数后，继续调用根左右节点的pathsum函数)：看题目要不要求从根节点开始的，还是从任意节点开始
一般路径：
vector<vector<int>>res;
void dfs(TreeNode*root,vector<int>path)
{
if(!root) return; //根节点为空直接返回
path.push_back(root->val); //作出选择
if(!root->left && !root->right) //如果到叶节点
{
res.push_back(path);
return;
}
dfs(root->left,path); //继续递归
dfs(root->right,path);
}
# **给定和的路径：**
void dfs(TreeNode*root, int sum, vector<int> path)
{
if (!root)
return;
sum -= root->val;
path.push_back(root->val);
if (!root->left && !root->right && sum == 0)
{
res.push_back(path);
return;
}
dfs(root->left, sum, path);
dfs(root->right, sum, path);
}
- 2.非自顶向下
设计一个辅助函数maxpath，调用自身求出以一个节点为根节点的左侧最长路径left和右侧最长路径right，那么经过该节点的最长路径就是left+right
接着只需要从根节点开始dfs,不断比较更新全局变量即可
1、left,right代表的含义要根据题目所求设置，比如最长路径、最大路径和等等
2、全局变量res的初值设置是0还是INT_MIN要看题目节点是否存在负值,如果存在就用INT_MIN，否则就是0
3、注意两点之间路径为1，因此一个点是不能构成路径的
int res=0;
int maxPath(TreeNode *root) //以root为路径起始点的最长路径
{
if (!root)
return 0;
int left=maxPath(root->left);
int right=maxPath(root->right);
res = max(res, left + right + root->val); //更新全局变量
return max(left, right); //返回左右路径较长者
}
