参考文章：一篇文章解决所有二叉树路径问题（问题分析+分类模板+题目剖析）
问题分类
二叉树路径问题大致分为两类：
1、自顶向下：
顾名思义，就是从某一个节点(不一定是根节点)，从上向下寻找路径，到某一个节点(不一定是叶节点)结束。具体题目如下：
二叉树的所有路径
面试题 04.12. 求和路径
路径总和
路径总和 II
路径总和 III
从叶结点开始的最小字符串
而继续细分的话还可以分成一般路径与给定和的路径。
2、非自顶向下：
就是从任意节点到任意节点的路径，不需要自顶向下。具体题目如下：
解题模板
这类题通常用深度优先搜索(DFS)和广度优先搜索(BFS)解决，BFS较DFS繁琐，这里为了简洁只展现DFS代码。
自顶向下
// 一般路径：
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);
}非自顶向下
这类题目一般解题思路如下：
设计一个辅助函数maxpath，调用自身求出以一个节点为根节点的左侧最长路径left和右侧最长路径right，那么经过该节点的最长路径就是left+right，接着只需要从根节点开始dfs,不断比较更新全局变量即可。
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); //返回左右路径较长者
}题目分析
自顶向下
二叉树的所有路径 257
直接套用模板1即可，注意把”->”放在递归调用中
class Solution {
public:
vector<string> res;
vector<string> binaryTreePaths(TreeNode* root) {
string path = "";
dfs(root, path);
return res;
}
void dfs(TreeNode* root, string path){
if(!root) return;
path += to_string(root->val);
if(!root->left && !root->right){ // 如果是叶子结点
res.push_back(path);
}
dfs(root->left, path + "->");
dfs(root->right, path + "->");
}
};路径总和 II 113
直接套用模板2
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<int> path;
dfs(root, targetSum, path);
return res;
}
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);
}
dfs(root->left, sum, path);
dfs(root->right, sum, path);
}
};路径总和 III 437
双重递归：先调用dfs函数从root开始查找路径，再调用pathsum函数到root左右子树开始查找
套用模板2
class Solution {
public:
int count = 0;
int pathSum(TreeNode* root, int targetSum) {
if(!root) return 0;
dfs(root, targetSum); //以root为起始点查找路径
pathSum(root->left, targetSum);
pathSum(root->right, targetSum);
return count;
}
void dfs(TreeNode* root, int sum){
if(!root) return;
sum -= root->val;
if(sum == 0) //注意不要return,因为不要求到叶节点结束,所以一条路径下面还可能有另一条
count++; //如果找到了一个路径全局变量就+1
dfs(root->left, sum);
dfs(root->right, sum);
}
};从叶结点开始的最小字符串 988
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<string> res;
string smallestFromLeaf(TreeNode* root) {
dfs(root, "");
sort(res.begin(), res.end());
return res[0];
}
void dfs(TreeNode* root, string path){
if(!root) return;
path += 'a' + root->val;
if(!root->left && !root->right){
reverse(path.begin(), path.end());
res.push_back(path);
}
dfs(root->left, path);
dfs(root->right, path);
}
};非自顶向下
二叉树中的最大路径和 124
left,right分别为根节点左右子树最大路径和,注意：如果最大路径和<0,意味着该路径和对总路径和做负贡献，因此不要计入到总路径中，将它设置为0。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int res = INT_MIN;
int maxPathSum(TreeNode* root) {
dfs(root);
return res;
}
int dfs(TreeNode* root){
if(!root) return 0;
//计算左边分支最大值，左边分支如果为负数还不如不选择
int left = max(0, dfs(root->left));
//计算右边分支最大值，右边分支如果为负数还不如不选择
int right = max(0, dfs(root->right));
//left->root->right 作为路径与已经计算过历史最大值做比较
res = max(res, left + right + root->val);
// 返回经过root的单边最大分支给当前root的父节点计算使用
return max(left + root->val, right + root->val);
}
};最长同值路径 687
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int res = 0;
int longestUnivaluePath(TreeNode* root) {
dfs(root);
return res;
}
int dfs(TreeNode* root){
if(!root) return 0;
// 左右路径
int left = dfs(root->left);
int right = dfs(root->right);
// 如果存在左子节点和根节点同值，更新左最长路径，否则左最长路径为0
if(root->left && root->val == root->left->val)
left++;
else left = 0;
if(root->right && root->val == root->right->val)
right++;
else right = 0;
res = max(res, left + right);
return max(left, right);
}
};二叉树的直径 543
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int res = INT_MIN;
int diameterOfBinaryTree(TreeNode* root) {
dfs(root);
return res;
}
int dfs(TreeNode* root){
if(!root) return 0;
int left = dfs(root->left);
int right = dfs(root->right);
res = max(res, left + right);
return max(left, right) + 1;
}
};
