目录
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;
}
};