深度遍历DFS（括号生成，二叉树所有路径）

        正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

注意的是

1. DFS 一定有一个边界值来跳出深度优先条件

2. 如果符合条件，马上来添加进入结果中

class Solution {
public:vector<string> generateParenthesis(int n) {vector<string> res;string str="";if(n<=0) {return res;}helper(res,str,n,n);return res;}void helper(vector<string>& strs, string str, int left, int right) {if(left<0||right<0||left>right) {return;}if(left==0&&right==0) {strs.emplace_back(str);}helper(strs,str+"(",left-1,right);helper(strs,str+")",left,right-1);}
};

257. 二叉树的所有路径https://leetcode.cn/problems/binary-tree-paths/

 

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

/*** 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> binaryTreePaths(TreeNode* root) {vector<string> result;string str;if(root==nullptr) {return result;}helper(root,result,"");return result;}void helper(TreeNode* root, vector<string> & result, string str) {str +=to_string(root->val);if(root->left==nullptr&&root->right==nullptr) {result.push_back(str);return;}// 区别的是这里需要来判断二叉树的节点是否为空指针节点，// 非空指针节点才能进行下一步的判断和处理if(root->left)  helper(root->left,  result,  str+"->");if(root->right) helper(root->right, result,  str+"->");}
};

112. 路径总和https://leetcode.cn/problems/path-sum/

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

/*** 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:bool hasPathSum(TreeNode* root, int targetSum) {if(root==nullptr) {return false;}return helper(root,targetSum);}bool helper(TreeNode* root, int targetSum) {if(root==nullptr) {return false;}if(root->left==nullptr&&root->right==nullptr) {return targetSum==root->val;}return helper(root->left,targetSum-root->val) || helper(root->right,targetSum-root->val);}
};