组合总和 III

问题描述

找出所有相加之和为 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]]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-iii

思路

这个题比较简单，用到的是回溯算法。
要解决的问题是在1~9之间选择k个数字，使得他们的和为n。每次选择的数字是1~9，因为不能重复，所以每次递归从上一次的位置加1开始，将每次递归的结果存到一个tmp数组里面，当tmp的size到k时，判断他们的和是否为n，如果为n，将tmp插入到ret，不管sum是否等于n，都要返回到上一层。返回到上一层后，千万别忘记，将sum减i，并且在tmp中弹出i；

题解

class Solution {
public:
    vector<int> tmp;
    vector<vector<int>> ret;
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k,n,0,1);
        return ret;
    }
    void dfs(int k,int n,int sum,int location){
        if(tmp.size()==k){
            if(sum==n){
                ret.push_back(tmp);
            }
            return;
        }
        for(int i=location;i<=9;i++){
            tmp.push_back(i);
            sum=sum+i;
            dfs(k,n,sum,i+1);
            sum=sum-i;
            tmp.pop_back();
        }

    }
};

最大二叉树

问题描述

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树，并且输出这个树的根节点。
Example 1:

输入: [3,2,1,6,0,5]
输入: 返回下面这棵树的根节点：

      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
注意:
给定的数组的大小在 [1, 1000] 之间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-binary-tree

思路

题解

从二叉搜索树到更大和树

问题描述

给出二叉搜索树的根节点，该二叉树的节点值各不相同，修改二叉树，使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键小于节点键的节点。
节点的右子树仅包含键大于节点键的节点。
左右子树也必须是二叉搜索树。

示例：

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree

思路

深度优先搜索

题解

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector <int> ret;
    int sum=0;
    TreeNode *bstToGst(TreeNode *root) {
        dfs(root);
        return root;
    }
    void dfs(TreeNode *node){
        if(node== nullptr) return;
        dfs(node->right);
        sum+=node->val;
        node->val=sum;
        dfs(node->left);
    }
};

组合

问题描述

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

思路

回溯算法

题解

class Solution {
public:
    vector<int> tmp;
    vector<vector<int>> ret;
    vector<vector<int>> combine(int n, int k) {
        dfs(n,k,1);
        return ret;
    }
    void dfs(int n,int k,int location){
        if(tmp.size()==k){
            ret.push_back(tmp);
            return ;
        }
        for(int i=location;i<=n;i++){
            tmp.push_back(i);
            dfs(n,k,i+1);
            tmp.pop_back();
        }
    }
};

二叉树的前序遍历

问题描述

给定一个二叉树，返回它的 前序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

思路

深度优先搜索。

题解

/**
 * 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> ret;
    vector<int> preorderTraversal(TreeNode* root) {
        dfs(root);
        return ret;
    }
    void dfs(TreeNode *node){
        if(node==nullptr){
            return ;
        }
        ret.push_back(node->val);
        dfs(node->left);
        dfs(node->right);
    }
};