目录
257. 二叉树的所有路径
题目描述：
输入输出描述：
思路和想法：
404. 左叶子之和
题目描述：
输入输出描述：
思路和想法：
513.找树左下角的值
题目描述：
输入输出描述：
思路和想法：
112. 路径总和
题目描述：
输入输出描述：
思路和想法：
113.路径总和ii
题目描述：
输入输出描述：
思路和想法：
257. 二叉树的所有路径
题目描述：
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
输入输出描述：
示例 1：
输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"]
示例 2：
输入：root = [1] 输出：["1"]
提示：
- 树中节点的数目在范围
[1, 100]内 -100 <= Node.val <= 100
思路和想法：
1.递归函数函数参数以及返回值
在参数方面，需要传入根节点node，记录每一条路径的path，和存放结果的result。这里的递归不需要返回值（为什么，这里）
2.确定递归终止条件
这里找到叶节点，当节点的左右孩子为空时，这个节点就是叶节点。
3.确定单层递归逻辑
确定为前序遍历：中左右，这里添加回溯过程path.pop_back();
class Solution {
public:
void getPath(TreeNode* node, vector<int> &path, vector<string>& result ){
path.push_back(node->val);
if(node->left == NULL && node->right == NULL){
string sPath;
for(int i = 0; i < path.size() - 1; i++){
sPath += to_string(path[i]);
sPath += "->";
}
sPath += to_string(path[path.size() - 1]);
result.push_back(sPath); //记录一个路径
}
//确定单层逻辑
if (node->left) {
getPath(node->left, path, result);
path.pop_back(); // 回溯
}
if (node->right) {
getPath(node->right, path, result);
path.pop_back(); // 回溯
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> result;
vector<int> path;
if (root == NULL) return result;
getPath(root, path, result);
return result;
}
};404. 左叶子之和
题目描述：
给定二叉树的根节点 root ，返回所有左叶子之和。
输入输出描述：
示例 1：
输入: root = [3,9,20,null,null,15,7] 输出: 24 解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
示例 2:
输入: root = [1] 输出: 0
提示:
- 节点数在
[1, 1000]范围内 -1000 <= Node.val <= 1000
思路和想法：
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if(root == NULL) return 0;
if(root->left == NULL && root->right == NULL) return 0;
int leftvalue = sumOfLeftLeaves(root->left);
if(root->left && !root->left->left && !root->left->right){
leftvalue = root->left->val;
}
int rightvalue = sumOfLeftLeaves(root->right);
int sum = leftvalue + rightvalue;
return sum;
}
};513.找树左下角的值
题目描述：
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
输入输出描述：
示例 1:
输入: root = [2,1,3] 输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7
提示:
- 二叉树的节点个数的范围是
[1,104] -2^31 <= Node.val <= 2^31 - 1
思路和想法：
这道题采用层序遍历比较明了直接，return最底层的第一数值。
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> que;
vector<vector<int>> result;
int BottomLeftValue = 0;
if(root != NULL) que.push(root); //弹入根节点
while(!que.empty()){
int size = que.size(); //记录size个数
vector<int> vec; //记录某一层的结果
while(size--){
TreeNode* node = que.front(); //获取要弹出的节点
que.pop(); //队列弹出
vec.push_back(node->val); //将弹出的节点数值放入数组中
if(node->left) que.push(node->left); //获取这个节点的左孩子
if(node->right) que.push(node->right); //获取这个节点的右孩子
}
result.push_back(vec); //将一层的数组放入到结果中
}
BottomLeftValue = result[result.size() - 1][0]; //获取结果最下面一行的第一个数值
return BottomLeftValue;
}
};112. 路径总和
题目描述：
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
输入输出描述：
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true 解释：等于目标和的根节点到叶节点路径如上图所示。
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：false 解释：树中存在两条根节点到叶子节点的路径： (1 --> 2): 和为 3 (1 --> 3): 和为 4 不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：
输入：root = [], targetSum = 0 输出：false 解释：由于树是空的，所以不存在根节点到叶子节点的路径。
提示：
- 树中节点的数目在范围
[0, 5000]内 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
思路和想法：
这道题运用到递归和回溯。如果最后count == 0，同时到了叶子节点的话，说明找到了目标和，就return true；未找到就回溯，看另一条路径是否符合；如果遍历到了叶子节点，count不为0，就是没找到。
class Solution {
public:
bool haspathsum(TreeNode* node, int count){
if(!node->left && !node->right && count == 0) return true; //遇到叶节点并且这条路径加和等于目标值时，返回true
if(!node->left && !node->right && count != 0) return false;
if(node->left){ //左
count -= node->left->val;
if(haspathsum(node->left, count)) return true;
count += node->left->val; //回溯
}
if(node->right){ //右
count -= node->right->val;
if(haspathsum(node->right, count)) return true;
count += node->right->val;
}
return false;
}
bool hasPathSum(TreeNode* root, int targetSum) {
if(root == NULL) return false;
return haspathsum(root, targetSum - root->val);
}
};113.路径总和ii
题目描述：
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点
输入输出描述：
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：[]
示例 3：
输入：root = [1,2], targetSum = 0 输出：[]
提示：
- 树中节点总数在范围
[0, 5000]内 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
思路和想法：
这道题是要遍历所有的路径，并找到相符的路径并输出，相比112题目，改变终止条件和输出即可
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void pathsum(TreeNode* node, int count){
if(!node->left && !node->right && count == 0){
result.push_back(path);
return;
}; //遇到叶节点并且这条路径加和等于目标值时
if(!node->left && !node->right && count != 0) return;
if(node->left){
path.push_back(node->left->val); //左
count -= node->left->val;
pathsum(node->left, count);
count += node->left->val; //回溯
path.pop_back();
}
if(node->right){ //右
path.push_back(node->right->val);
count -= node->right->val;
pathsum(node->right, count);
count += node->right->val;
path.pop_back();
}
return;
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
result.clear();
path.clear();
if(root == nullptr) return result;
path.push_back(root->val);
pathsum(root, targetSum - root->val);
return result;
}
};
