潍坊网站设计公司,自媒体平台前十名,自己做网站美工,湛江网站建设优化推广正整数 n 代表生成括号的对数#xff0c;请设计一个函数#xff0c;用于能够生成所有可能的并且 有效的 括号组合。
示例 1#xff1a;
输入#xff1a;n 3
输出#xff1a;[((())),(()()),(())(),()(()),()()(… 正整数 n 代表生成括号的对数请设计一个函数用于能够生成所有可能的并且 有效的 括号组合。
示例 1
输入n 3
输出[((())),(()()),(())(),()(()),()()()]示例 2
输入n 1
输出[()]注意的是
1. DFS 一定有一个边界值来跳出深度优先条件
2. 如果符合条件马上来添加进入结果中 class Solution {
public:vectorstring generateParenthesis(int n) {vectorstring res;string str;if(n0) {return res;}helper(res,str,n,n);return res;}void helper(vectorstring strs, string str, int left, int right) {if(left0||right0||leftright) {return;}if(left0right0) {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:vectorstring binaryTreePaths(TreeNode* root) {vectorstring result;string str;if(rootnullptr) {return result;}helper(root,result,);return result;}void helper(TreeNode* root, vectorstring result, string str) {str to_string(root-val);if(root-leftnullptrroot-rightnullptr) {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(rootnullptr) {return false;}return helper(root,targetSum);}bool helper(TreeNode* root, int targetSum) {if(rootnullptr) {return false;}if(root-leftnullptrroot-rightnullptr) {return targetSumroot-val;}return helper(root-left,targetSum-root-val) || helper(root-right,targetSum-root-val);}
};
