问题 中等
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。 解集不能包含重复的组合。 示例 1:
输入: k = 3, n = 7 输出: [[1,2,4]] 示例 2:
输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
my way
回溯法
循环加递归，还有改进空间，有重复计算过程
class Solution { public: vector<vector<int>> combinationSum(int k, int n,int m){ vector<vector<int>> tmp; if(k==1){ for(int i=m;i<=9;i++) if(i==n){ vector<int> tmp1; tmp1.push_back(i); tmp.push_back(tmp1); } return tmp; } for(int i=m;i<=10-k;i++){ vector<vector<int>> tmp0; tmp0 = combinationSum(k-1,n-i,i+1) ; for(int j=0;j<tmp0.size();j++){ tmp0[j].insert(tmp0[j].begin(),i); } tmp.insert(tmp.end(),tmp0.begin(),tmp0.end()); } return tmp; } vector<vector<int>> combinationSum3(int k, int n) { vector<vector<int>> tmp; for(int i=1;i<=10-k;i++){ vector<vector<int>> tmp0; tmp0 = combinationSum(k-1,n-i,i+1); for(int j=0;j<tmp0.size();j++){ tmp0[j].insert(tmp0[j].begin(),i); } tmp.insert(tmp.end(),tmp0.begin(),tmp0.end()); } return tmp; } }; 时间复杂度 O(k!)空间复杂度 空间复杂度：O(M)。temp 数组的空间代价是 O(k)，递归栈空间的代价是 O(M)，故空间复杂度为 O(M + k) = O(M)官方解答
思路类似于我的方法，都是寻找所有组合方法一个个判断。
class Solution{ public: vector<int> temp; vector<vector<int>> ans; void dfs(int cur,int n, int k, int sum){ if(temp.size() + (n-cur +1)<k || temp.size() >k){ return; } if(temp.size() == k && accumulate(temp.begin(),temp.end(),0) == sum){ ans.push_back(temp); return; } temp.push_back(cur); dfs(cur+1,n,k,sum); temp.pop_back(); dfs(cur+1,n,k,sum); } vector<vector<int>> combinationSum3(int k,int n){ dfs(1,9,k,n); return ans; } } 时间复杂度：O({M \choose k} \times k)O(( kM)×k)，其中 M 为集合的大小，本题中 M 固定为 9。一共有 M \choose k( kM ) 个组合，每次判断需要的时间代价是 O(k)。空间复杂度：O(M)。temp 数组的空间代价是 O(k)，递归栈空间的代价是 O(M)，故空间复杂度为 O(M + k) = O(M)问题 简单
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
示例 1：
输入： 3 / 9 20 / 15 7 输出：[3, 14.5, 11] 解释： 第 0 层的平均值是 3 , 第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
my way
使用队列层次遍历二叉树，并使用另一个队列作为flag，标志每一层的结束。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<double> averageOfLevels(TreeNode* root) { queue<TreeNode*> s; queue<int> flag; vector<double> result; double sum_cur=0; double l = 0; s.push(root); flag.push(0); while(!s.empty()){ int tmp=flag.front(); TreeNode* cur = s.front(); s.pop(); flag.pop(); sum_cur+=cur->val; l++; if(flag.empty() || tmp!= flag.front()){ result.push_back(sum_cur/l); l=0; sum_cur=0; } if(cur->left!=NULL){ s.push(cur->left); flag.push(!tmp); } if(cur->right!=NULL){ s.push(cur->right); flag.push(!tmp); } } return result; } }; 时间复杂度O(n), 其中n是二叉树中的节点个数。空间复杂度O(n)官方解答之 广度优先遍历
类似于我的方法。
比我的更好，不需要flag，直接将每一层的队列节点全部取出，需要在遍历每一层之前获取每一层的size。
class Solution{ public: vector<double> averageOfLevels(TreeNode* root) { auto averages = vector<double>(); auto q = queue<TreeNode*>(); q.push(root); while (!q.empty()) { double sum = 0; int size = q.size(); for (int i = 0; i < size; i++) { auto node = q.front(); q.pop(); sum += node->val; auto left = node->left, right = node->right; if (left != nullptr) { q.push(left); } if (right != nullptr) { q.push(right); } } averages.push_back(sum / size); } return averages; } }; 时间复杂度：O(n)，其中 n 是二叉树中的节点个数空间复杂度：O(n)官方解答之 深度优先遍历
class Solution { public: vector<double> averageOfLevels(TreeNode* root) { auto counts = vector<int>(); auto sums = vector<double>(); dfs(root, 0, counts, sums); auto averages = vector<double>(); int size = sums.size(); for (int i = 0; i < size; i++) { averages.push_back(sums[i] / counts[i]); } return averages; } void dfs(TreeNode* root, int level, vector<int> &counts, vector<double> &sums) { if (root == nullptr) { return; } if (level < sums.size()) { sums[level] += root->val; counts[level] += 1; } else { sums.push_back(1.0 * root->val); counts.push_back(1); } dfs(root->left, level + 1, counts, sums); dfs(root->right, level + 1, counts, sums); } };时间复杂度：O(n)，其中 nn 是二叉树中的节点个数。 深度优先搜索需要对每个节点访问一次，对于每个节点，维护两个数组的时间复杂度都是 O(1)，因此深度优先搜索的时间复杂度是 O(n)。 遍历结束之后计算每层的平均值的时间复杂度是 O(h)，其中 hh 是二叉树的高度，任何情况下都满足 h≤n。 因此总时间复杂度是 O(n)。
空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度取决于两个数组的大小和递归调用的层数，两个数组的大小都等于二叉树的高度，递归调用的层数不会超过二叉树的高度，最坏情况下，二叉树的高度等于节点个数
问题
给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3] 1 2 / 3
输出: [1,3,2] 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
递归解法
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> result ; vector<int> inorderTraversal(TreeNode* root) { if(root==NULL) return result; dfs(root); return result; } void dfs(TreeNode* root){ if(root==NULL) return ; dfs(root->left); result.push_back(root->val); dfs(root->right); return; } }; 时间复杂度O (n) ,n为二叉树的节点数空间复杂度O(n), （不包括结果占用的空间） 递归的次数，最坏情况下为n迭代
非递归算法
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> stk; while(root != nullptr || !stk.empty()){ while(root!=nullptr){ stk.push(root); root = root->left; } root = stk.top(); stk.pop(); res.push_back(root->val); root = root->right; } return res; } }; 时间复杂度:O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。空间复杂度：O(n)。空间复杂度取决于栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别。Morris中序遍历
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> res; TreeNode *predecessor = nullptr; while (root != nullptr) { if (root->left != nullptr) { // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止 predecessor = root->left; while (predecessor->right != nullptr && predecessor->right != root) { predecessor = predecessor->right; } // 让 predecessor 的右指针指向 root，继续遍历左子树 if (predecessor->right == nullptr) { predecessor->right = root; root = root->left; } // 说明左子树已经访问完了，我们需要断开链接 else { res.push_back(root->val); predecessor->right = nullptr; root = root->right; } } // 如果没有左孩子，则直接访问右孩子 else { res.push_back(root->val); root = root->right; } } return res; } }; 时间复杂度：O(n)，其中 n 为二叉搜索树的节点个数。Morris 遍历中每个节点会被访问两次，因此总时间复杂度为O(2n)=O(n)。空间复杂度：O(1)。问题 中等
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]
我的程序
莫得，我没做出来。
搜索回溯
class Solution{ vector<int> vis; public: void backtrack(vector<int>& nums,vector<int>>& ans,int idx,vector<int>& perm){ if(idx == nums.size()){ ans.emplace_back(perm); return; } for(int i=0;i<(int)nums.size();++i){ if(vis[i] || (i>0 && nums[i] == nums[i-1] && !vis[i-1])){ continue; } perm.emplace_back(nums[i]); vis[i] = 1; backtrack(nums,ans,idx+1,perm); vis[i] = 0; perm.pop_back(); } } vector<vector<int>> permuteUnique(vector<int>& nums){ vector<vector<int>> ans; vector<int> perm; vis.resize(nums.size()); sort(nums.begin().nums.end()); backtrack(nums,ans,0,perm); return ans; } } 时间复杂度O(n*n!),其中n为序列的长度空间复杂度O(n)问题
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
my way
回溯搜索法
class Solution { public: vector<vector<int>> result; vector<vector<int>> subsets(vector<int>& nums) { vector<int> tmp; backtrack(tmp,nums,0); return result; } void backtrack(vector<int> tmp,vector<int>& nums,int t){ if(nums.begin()+t == nums.end()){ result.push_back(tmp); return; } backtrack(tmp,nums,t+1); tmp.push_back(*(nums.begin()+t)); backtrack(tmp,nums,t+1); return; } }; 时间复杂度空间复杂度不会算。。。。
迭代法实现子集枚举
class Solution { public: vector<int> t; vector<vector<int>> ans; vector<vector<int>> subsets(vector<int>& nums) { int n = nums.size(); for (int mask = 0; mask < (1 << n); ++mask) { t.clear(); for (int i = 0; i < n; ++i) { if (mask & (1 << i)) { t.push_back(nums[i]); } } ans.push_back(t); } return ans; } } 时间复杂度：O(n*2^n)一共 2^n个状态，每种状态需要O(n) 的时间来构造子集。空间复杂度：O(n)。即构造子集使用的临时数组 t 的空间代价递归法实现自己枚举
class Solution { public: vector<int> t; vector<vector<int>> ans; void dfs(int cur, vector<int>& nums) { if (cur == nums.size()) { ans.push_back(t); return; } t.push_back(nums[cur]); dfs(cur + 1, nums); t.pop_back(); dfs(cur + 1, nums); } vector<vector<int>> subsets(vector<int>& nums) { dfs(0, nums); return ans; } }; 时间复杂度：O(n * 2 ^ n) )。一共 2^n个状态，每种状态需要O(n) 的时间来构造子集。空间复杂度 O(n)。临时数组 tt 的空间代价是 O(n)，递归时栈空间的代价为 O(n)。问题
给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
例如：
输入: 原始二叉搜索树: 5 / 2 13
输出: 转换为累加树: 18 / 20 13
反序中序遍历
class Solution { public: int sum = 0; TreeNode* convertBST(TreeNode* root){ if(root != nullptr){ convertBST(root->right); sum+=root->val; root->val=sum; convertBST(root->left); } return root; } }; 时间复杂度O(n)，n是二叉树的节点数空间复杂度O(n), 为递归过程中的栈的开销，平均情况下O(logn),最坏情况下为链状，O(n).**问题 ** 简单
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
输入: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 输出: 合并后的树: 3 / 4 5 / \ \ 5 4 7 注意: 合并必须从两个树的根节点开始。
深度优先搜索
class Solution { public: TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) { if(t1==nullptr) return t2; if(t2==nullptr) return t1; TreeNode* root=new TreeNode(); root->val=t1->val+t2->val; root->right=mergeTrees(t1->right,t2->right); root->left=mergeTrees(t1->left,t2->left); return root; } }; 时间复杂度O(min(m,n)) m, n为2个树各自节点个数时间复杂度O(min(m,n)问题
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例: 给定如下二叉树，以及目标和 sum = 22，
5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1返回:
[ [5,4,11,2], [5,8,4,5] ]
深度优先搜索
class Solution { public: vector<vector<int>> result; vector<int> cur_num; int cur_sum=0; void dfs(TreeNode* root, int sum){ if(root==nullptr) return; cur_num.push_back(root->val); cur_sum+=root->val; if(cur_sum==sum && root->right==nullptr && root->left==nullptr){ result.push_back(cur_num); } else{ dfs(root->left,sum); dfs(root->right,sum); } cur_num.pop_back(); cur_sum-=root->val; return; } vector<vector<int>> pathSum(TreeNode* root, int sum) { dfs(root,sum); return result; } }; 时间复杂度O(n^2) ,n为节点数,在最坏情况下，树的上半部分为链状，下半部分为完全二叉树，并且从根节点到每一个叶子节点的路径都符合题目要求。此时，路径的数目为 O(N)，并且每一条路径的节点个数也为 O(N)，因此要将这些路径全部添加进答案中，时间复杂度为 O(N^2)空间复杂度O(n), path空间，最坏情况下n问题 简单
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。 示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。 p、q 为不同节点且均存在于给定的二叉搜索树中。
一次遍历
根据二叉搜索树的特点可知，从根节点开始遍历，若qp的值都小于当前节点的值，则当前节点指向左子树，反之则指向右子树；若当前节点的值位于中间位置，则当前节点应当是公共祖先节点。
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { TreeNode* curnode=root; while(true){ if(curnode->val > p->val && curnode->val > q->val){ curnode = curnode->left; } else if(curnode->val < p->val && curnode->val < q->val){ curnode = curnode->right; } else break; } return curnode; } }; 时间复杂度O(n) n为节点数空间复杂度O(1)问题 中等
给定一个二叉树
struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
进阶：
你只能使用常量级额外空间。 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
示例：
输入：root = [1,2,3,4,5,null,7] 输出：[1,#,2,3,#,4,5,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
提示：
树中的节点数小于 6000 -100 <= node.val <= 100
广度优先遍历
使用了一个队列空间
/* // Definition for a Node. class Node { public: int val; Node* left; Node* right; Node* next; Node() : val(0), left(NULL), right(NULL), next(NULL) {} Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {} Node(int _val, Node* _left, Node* _right, Node* _next) : val(_val), left(_left), right(_right), next(_next) {} }; */ class Solution { public: Node* connect(Node* root) { queue<Node*> tmp; if(root==nullptr) return root; tmp.push(root); while(!tmp.empty()){ int len = tmp.size(); for(int i=0;i<len;i++){ Node* cur = tmp.front(); tmp.pop(); if(cur->left!=nullptr) tmp.push(cur->left); if(cur->right!=nullptr) tmp.push(cur->right); if(i==len-1){ cur->next = NULL; } else{ cur->next = tmp.front(); } } } return root; } }; 时间复杂度O(n);空间复杂度O(n);使用已建立的next指针
降低空间复杂度。。。
不会做，看不懂！！！！！！！！！！
先抄一段代码，CV大法好。
具体来说：
从根节点开始。因为第 00 层只有一个节点，不需要处理。可以在上一层为下一层建立 \rm nextnext 指针。该方法最重要的一点是：位于第 xx 层时为第 x + 1x+1 层建立 \rm nextnext 指针。一旦完成这些连接操作，移至第 x + 1x+1 层为第 x + 2x+2 层建立 \rm nextnext 指针。 当遍历到某层节点时，该层节点的 \rm nextnext 指针已经建立。这样就不需要队列从而节省空间。每次只要知道下一层的最左边的节点，就可以从该节点开始，像遍历链表一样遍历该层的所有节点。
public: void handle(Node* &last, Node* &p, Node* &nextStart) { if (last) { last->next = p; } if (!nextStart) { nextStart = p; } last = p; } Node* connect(Node* root) { if (!root) { return nullptr; } Node *start = root; while (start) { Node *last = nullptr, *nextStart = nullptr; for (Node *p = start; p != nullptr; p = p->next) { if (p->left) { handle(last, p->left, nextStart); } if (p->right) { handle(last, p->right, nextStart); } } start = nextStart; } return root; } }; 时间复杂度：O(N)。分析同「方法一」。空间复杂度：O(1)问题 中等
给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3] 1 \ 2 / 3 输出: [3,2,1]进阶: 递归算法很简单，你可以通过迭代算法完成吗？
递归
/** * 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<int> result; vector<int> postorderTraversal(TreeNode* root) { postorder(root); return result; } void postorder(TreeNode* root){ if(root==nullptr) return; postorder(root->left); postorder(root->right); result.push_back(root->val); return; } }; 时间复杂度O(n), n为节点数空间复杂度O(n), 递归隐式栈占用的空间，平均情况下为 O(log n)，最坏情况下树呈现链状，为 O(n)。迭代
隐式栈变成显式栈
后序遍历 左-右-中 ， 可以改成中-右-左，最后翻转下
/** * 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<int> postorderTraversal(TreeNode* root) { vector<int> result; if(root==nullptr) return result; stack<TreeNode*> tmp; tmp.push(root); while(!tmp.empty()){ TreeNode* cur = tmp.top(); tmp.pop(); result.push_back(cur->val); if(cur->left!=nullptr){ tmp.push(cur->left); } if(cur->right!=nullptr){ tmp.push(cur->right); } } reverse(result.begin(),result.end()); return result; } }; 时间复杂度O(n)空间复杂度O(n)问题 中等
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
例如,
给定二叉搜索树:
4 / \ 2 7 / \ 1 3和 插入的值: 5 你可以返回这个二叉搜索树:
4 / \ 2 7 / \ / 1 3 5或者这个树也是有效的:
5 / \ 2 7 / \ 1 3 \ 4提示：
给定的树上的节点数介于 0 和 10^4 之间 每个节点都有一个唯一整数值，取值范围从 0 到 10^8 -10^8 <= val <= 10^8 新值和原始二叉搜索树中的任意节点值都不同
递归
根据二叉搜索树的性质，插入节点的话，若该值大于当前节点值，这肯定要插到当前节点的右子树，否则插入到左子树。递归下去，直到当前节点为空，则插入该值。
/** * 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: TreeNode* insertIntoBST(TreeNode* root, int val) { if(root==nullptr){ root = new TreeNode(val); return root; } if(val > root->val) root->right= insertIntoBST(root->right,val); else root->left = insertIntoBST(root->left,val); return root; } }; 时间复杂度O(n) ,n为节点数目，最坏情况下，该树为链状。空间复杂度O(n) 递归的栈开销。模拟（算是迭代吧）
算法和上一个解法一样
class Solution { public: TreeNode* insertIntoBST(TreeNode* root, int val) { if (root == nullptr) { return new TreeNode(val); } TreeNode* pos = root; while (pos != nullptr) { if (val < pos->val) { if (pos->left == nullptr) { pos->left = new TreeNode(val); break; } else { pos = pos->left; } } else { if (pos->right == nullptr) { pos->right = new TreeNode(val); break; } else { pos = pos->right; } } } return root; } }; 时间复杂度O(n) root = new TreeNode(val); return root; } if(val > root->val) root->right= insertIntoBST(root->right,val); else root->left = insertIntoBST(root->left,val); return root; } }; - 时间复杂度O(n) ,n为节点数目，最坏情况下，该树为链状。 - 空间复杂度O(n) 递归的栈开销。 **模拟（算是迭代吧）** 算法和上一个解法一样 ~~~cpp class Solution { public: TreeNode* insertIntoBST(TreeNode* root, int val) { if (root == nullptr) { return new TreeNode(val); } TreeNode* pos = root; while (pos != nullptr) { if (val < pos->val) { if (pos->left == nullptr) { pos->left = new TreeNode(val); break; } else { pos = pos->left; } } else { if (pos->right == nullptr) { pos->right = new TreeNode(val); break; } else { pos = pos->right; } } } return root; } }; 时间复杂度O(n)空间复杂度O(1)9月水水水！！
