1
2
3
4
5
6
7
8
 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) {}
 };

1
2
3
4
5
6
7
8
class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) { val = _val; }
    Node(int _val, vector<Node*> _children) { val = _val;children = _children; }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * 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:
    // 1、确定递归函数的参数和返回值   &nums必须按地址传递
    void Traversal(TreeNode *cur,vector<int> &nums){
        //2、确定终止条件
        if(cur==nullptr) return;                          
        //3、确定单层递归的逻辑
        nums.push_back(cur->val);    //中
        Traversal(cur->left,nums);   //左
        Traversal(cur->right,nums);  //右
    }
    vector<int> preorderTraversal(TreeNode* root) {
       vector<int> ans;
       Traversal(root,ans);
       return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 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> preorderTraversal(TreeNode* root) {
       vector<int> ans;    //将元素放入ans数组中
       if(root==nullptr) return ans;
       stack<TreeNode*> stk;
       stk.push(root);       //中（根）
       while(!stk.empty()){
            TreeNode* node=stk.top();
            stk.pop();

            ans.push_back(node->val);                //中
            if(node->right)  stk.push(node->right);  //右，空节点不入栈
            if(node->left)  stk.push(node->left);    //左，空节点不入栈
       }
       return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 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> preorderTraversal(TreeNode* root) {
     vector<int> ans;
     stack<TreeNode*> stk;
     if(root!=nullptr) stk.push(root);
     while(!stk.empty()){
         TreeNode* node=stk.top();
         if(node!=nullptr){
             stk.pop();    //将根节点弹出，避免重复操作，，无此步，会超时

             if(node->right) stk.push(node->right);  //右
             if(node->left) stk.push(node->left);     //左
             stk.push(node);                          //中
             stk.push(nullptr);
         }
         else{
             stk.pop();
             node=stk.top();
             stk.pop();
             ans.push_back(node->val);
         }
     }
     return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 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:
    void Traversal(TreeNode *node,vector<int> &vec){
        if(node==nullptr) return;
        Traversal(node->left,vec);
        vec.push_back(node->val);
        Traversal(node->right,vec);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        Traversal(root,ans);
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 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> inorderTraversal(TreeNode* root) {
       stack<TreeNode*> stk;
       vector<int> ans;
       TreeNode* node=root;
       while(node!=nullptr || !stk.empty()){
           if(node!=nullptr){
               stk.push(node);   //指针访问节点，访问到最底层，将访问的节点放入栈中
               node=node->left;  //左
           }
           else{
               //栈中弹出的数据就是要处理的数据，即要放入ans数组里的数据
               node=stk.top();
               stk.pop();
               ans.push_back(node->val);  //中               
               node=node->right;          //右
           }
       }
       return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * 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> inorderTraversal(TreeNode* root) {
     vector<int> ans;  //存放结果
     stack<TreeNode*> stk;
     if(root!=nullptr) stk.push(root);  //将根节点放入栈中
     while(!stk.empty()){
         TreeNode* node = stk.top();   //取出栈中元素
         if(node!=nullptr){
             stk.pop();             //将节点弹出，避免重复操作
             if(node->right) stk.push(node->right);  //右  空节点不入栈
             stk.push(node);        //中
             stk.push(nullptr);     //中节点访问过，但是还没有处理， 加入空节点做标记
             if(node->left)   stk.push(node->left);  //左  空节点不入栈
         }

         else{
             //空节点做的标记，只有遇到空节点时，才将下一个节点放入结果集
             stk.pop();        //将空节点弹出
             node=stk.top();   //重新取出栈中元素
             stk.pop();
             ans.push_back(node->val);  //加入到结果集
         }
     }
     return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 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:
    void Traversal(TreeNode *root,vector<int> &vec){
        if(root==nullptr) return;
        Traversal(root->left,vec);    //是root->left,而不是vec->left
        Traversal(root->right,vec);
        vec.push_back(root->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;       //ans用于存放遍历后的二叉树
        Traversal(root,ans);
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 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> ans;
       if(root==nullptr) return ans;
       stack<TreeNode*> stk;
       stk.push(root);
       while(!stk.empty()){
           TreeNode* node=stk.top();
           stk.pop();

           ans.push_back(node->val);
           if(node->left) stk.push(node->left);  //相对于前序遍历，这更改一下入栈顺序
           if(node->right) stk.push(node->right);
       }
       reverse(ans.begin(),ans.end());
       return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 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) {
      stack<TreeNode*> stk;
      vector<int> ans;
      if(root!=nullptr)  stk.push(root);
      while(!stk.empty()){
          TreeNode* node=stk.top();
          if(node!=nullptr){
              stk.pop();       //将该节点弹出，避免重复操作
              stk.push(node);
              stk.push(nullptr);
              if(node->right)  stk.push(node->right);
              if(node->left)   stk.push(node->left);
          }
          else{
              stk.pop();      //将空节点弹出
              node=stk.top();
              stk.pop();
              ans.push_back(node->val);
          }
      }
      return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
private:
    bool Traversal(vector<int>& postorder,int i,int j){
        if(i>=j) return true;  // 此子树节点数量 ≤1，无需判别正确性，因此直接返回 true
        //寻找第一个大于根节点的节点，切分数组
        int p=i;
        while(postorder[p]<postorder[j]) p++;
        int m=p;
        //遍历右子树
        while(postorder[p]>postorder[j]) p++;

        //根节点p=j; 左子树[i,m-1]; 右子树[m,j-1]
        return p==j && Traversal(postorder,i,m-1) && Traversal(postorder,m,j-1);
    }
public:
    bool verifyPostorder(vector<int>& postorder) {
        return Traversal(postorder,0,postorder.size()-1);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 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<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> que;         //队列先进先出，符合一层一层遍历的逻辑,故使用队列实现二叉树广度优先遍历,,,,,元素为二叉树
        if(root!=nullptr) que.push(root);

        while(!que.empty()){
            vector<int> vec;
            int size=que.size();
            for(int i=0;i<size;++i){ // 这里一定要使用固定大小size，不要使用que.size()，因为que.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);    //错误代码 vec.push(),  que_push_back()
            }
            ans.push_back(vec);
       }
       return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 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<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>>  ans;
        queue<TreeNode*> que;
        if(root!=nullptr) que.push(root);
        while(!que.empty()){
            vector<int> vec;
            int size=que.size();
            for(int i=0;i<size;++i){            
                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);
            }
            ans.push_back(vec);
        }
        reverse(ans.begin(),ans.end());  //不同：反转一下数组即可
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> ans;
        queue<TreeNode*> que;
        if(root!=NULL) que.push(root);
        while(!que.empty()){           
            int size=que.size();
            for(int i=0;i<size;++i){
                TreeNode *node=que.front();
                que.pop();
                ans.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> que;
        if(root!=NULL) que.push(root);
        while(!que.empty()){
            vector<int> vec;
            int size=que.size();
            for(int i=0;i<size;++i){
                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);
            }
            ans.push_back(vec);
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> que;
        if(root!=NULL) que.push(root);
        while(!que.empty()){
            vector<int> vec;
            int size=que.size();
            for(int i=0;i<size;++i){
                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);
            }
            // 若 ans 的长度为 奇数 ，说明当前是偶数层，则对 vec 执行 倒序 操作。
            if(ans.size()%2==1) reverse(vec.begin(),vec.end());
            ans.push_back(vec);
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 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> rightSideView(TreeNode* root) {
        vector<int> ans;
        queue<TreeNode*> que;
        if(root!=nullptr) que.push(root);
        while(!que.empty()){
            int size=que.size();
            for(int i=0;i<size;++i){
                 TreeNode* node=que.front();
                 que.pop();  
          
                 if(i==(size-1))  ans.push_back(node->val);  //将每一层的最后一个元素放入ans数组中,之前是所有的元素全部放入数组中

                 if(node->left) que.push(node->left);
                 if(node->right) que.push(node->right);
           }
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> ans;
        queue<TreeNode*> que;
        if(root!=nullptr) que.push(root);
        while(!que.empty()){
            int size=que.size();
            double sum=0;   // 统计每一层的和
            for(int i=0;i<size;++i){
                TreeNode* node=que.front();
                que.pop();

                sum+=node->val;
          
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            ans.push_back(sum/size);   将每一层均值放进结果集，不是除以que.size()
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> ans;
        queue<TreeNode*> que;
        if(root!=nullptr) que.push(root);
        while(!que.empty()){
            int size=que.size();
            int maxValue=INT_MIN;
            for(int i=0;i<size;++i){
                TreeNode* node=que.front();
                que.pop();

                maxValue=node->val >maxValue? node->val :maxValue;
                // maxValue=max(node->val,maxValue);

                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            ans.push_back(maxValue);
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 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> largestValues(TreeNode* root) {
     vector<int> ans;
     queue<TreeNode*> que;
     if(root!=nullptr) que.push(root);
     while(!que.empty()){
         int size=que.size();
         vector<int> vec;
         for(int i=0;i<size;++i){
             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);
         }
         sort(vec.begin(),vec.end(),greater<int>());
         ans.push_back(vec[0]);
     }
     return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*// 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*> que;
        if(root!=NULL) que.push(root);

        while(!que.empty()){                // 1、外层的 while 循环迭代的是层数
            int size=que.size();            // 记录当前队列大小           
            for(int i=0; i<size; ++i){      // 2、遍历这一层的所有节点
                Node *node = que.front();
                que.pop();

                if(i != size-1) node->next = que.front();   // 连接
                
                if(node->left)  que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return root;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if(root!=NULL) que.push(root);

        while(!que.empty()){                // 1、外层的 while 循环迭代的是层数
            int size=que.size();            // 记录当前队列大小           
            for(int i=0; i<size; ++i){      // 2、遍历这一层的所有节点
                Node *node = que.front();
                que.pop();

                // 连接
                if(i != size-1){
                    node->next = que.front();
                }else{
                    node->next = NULL;
                }
                
                if(node->left)  que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return root;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) {
        val = _val;
    }
    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};*/
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ans;
        queue<Node*> que;
        if(root!=nullptr) que.push(root);
        while(!que.empty()){
            vector<int> vec;
            int size=que.size();
            for(int i=0;i<size;++i){
                Node* node=que.front();
                que.pop();
                vec.push_back(node->val);   //传入val,而不是_val

                //将节点孩子加入队列
                for(int i=0;i<node->children.size();++i){
                    if(node->children[i])   que.push(node->children[i]);
                }
            }
            ans.push_back(vec);
        }
        return ans ;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * 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:
    //层序遍历的层数就是二叉树的最大深度
    int maxDepth(TreeNode* root) {
       if(root==nullptr)  return 0;
       int depth=0;
       queue<TreeNode*> que;
       que.push(root);
       while(!que.empty()){
           int size=que.size();
           depth++;  //记录深度
           for(int i=0;i<size;++i){
               TreeNode *node=que.front();
               que.pop();
               if(node->left) que.push(node->left);
               if(node->right) que.push(node->right);
           }
       }
       return depth;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 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:
    int getDepth(TreeNode *root){
        if(root==nullptr) return 0;
        int leftDepth  = getDepth(root->left);
        int rightDepth = getDepth(root->right);
        return 1+max(leftDepth,rightDepth);
    }
    int maxDepth(TreeNode* root) {
        return getDepth(root);
    }
};
/*   //简化
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==nullptr)  return 0;
        return 1+max(maxDepth(root->left),maxDepth(root->right));
    }
}; */

1
2
3
4
5
6
7
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL) return 0;
        return 1+max(maxDepth(root->left),maxDepth(root->right));
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) {
        val = _val;
    }
    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};*/

class Solution {
public:
    int maxDepth(Node* root) {
        if(root==nullptr) return 0;    
        int depth=0;
        queue<Node*> que;
        que.push(root);
        while(!que.empty()){
            int size=que.size();
            depth++;
            for(int i=0;i<size;++i){
                Node *node=que.front();
                que.pop();
                //将节点孩子加入队列
                for(int i=0;i< node->children.size();++i){
                    if(node->children[i]) que.push(node->children[i]);
                }
            }
        }
        return depth;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) {
        val = _val;
    }
    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};*/

class Solution {
public:
    int maxDepth(Node* root) {
        if(root==nullptr) return 0;    
        int maxChildDepth=0;
        vector<Node*> children=root->children;
        for(auto child : children){
            maxChildDepth=max(maxChildDepth,maxDepth(child));
        }
        return 1+maxChildDepth;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * 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:
    int minDepth(TreeNode* root) {
      if(root==nullptr) return 0;
      int depth=0;
      queue<TreeNode*> que;
      que.push(root);
      while(!que.empty()){
         int size=que.size();
         depth++;
         for(int i=0;i<size;++i){
             TreeNode *node=que.front();
             que.pop();
             if(node->left) que.push(node->left);
             if(node->right) que.push(node->right);
             //遇到左右孩子为空，就找到了最小深度，就会提前return
             if(!node->left && !node->right) return depth;    
         }
      }
      return depth;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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:
    int minDepth(TreeNode* root) {
        if(root==nullptr) return 0;
        if(root->left==nullptr && root->right!=nullptr) 
        return 1+minDepth(root->right);
        if(root->left!=nullptr && root->right==nullptr)
        return 1+minDepth(root->left);

        return 1+min(minDepth(root->left),minDepth(root->right));
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * 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:
    //返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树则返回-1
    int getHeight(TreeNode* node){
        if(node==nullptr) return 0;
        if(getHeight(node->left)==-1 || getHeight(node->right)==-1 || abs(getHeight(node->left)-getHeight(node->right))>1)  return -1;
        else return 1+max(getHeight(node->left),getHeight(node->right)); // 以当前节点为根节点的树的最大高度

        //if(getHeight(node->left)==-1) return -1;
        //if(getHeight(node->right)==-1) return -1;

        //if(abs(getHeight(node->left)-getHeight(node->right))>1) return -1;
        //else return 1+max(getHeight(node->left),getHeight(node->right));    
        //return abs(getHeight(node->left)-getHeight(node->right))>1 ? -1 : 1+max(getHeight(node->left),getHeight(node->right));
    }
    bool isBalanced(TreeNode* root) {
      return getHeight(root)>=0;
      //return getHeight(root)==-1?false:true;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
private:
    int getHeight(TreeNode* root){
        if(root==NULL) return 0;
        int leftHeight=getHeight(root->left);
        int rightHeight=getHeight(root->right);
        if(leftHeight==-1||rightHeight==-1||abs(leftHeight-rightHeight)>1){
            return -1;
        }else{
            return 1+max(leftHeight,rightHeight);
        }
    }
public:
    bool isBalanced(TreeNode* root) {
        return getHeight(root)>=0;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 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* invertTree(TreeNode* root) {
      queue<TreeNode*> que;
      if(root!=nullptr) que.push(root);
      while(!que.empty()){
         int size=que.size();
         for(int i=0;i<size;++i){
             TreeNode *node=que.front();
             que.pop();
             swap(node->left,node->right);
             if(node->left)  que.push(node->left);
             if(node->right) que.push(node->right);
         }
      }
      return root;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 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:   
    //递归三部曲：1、确定递归函数的参数和返回值
    TreeNode* invertTree(TreeNode* root) {
        //2、确定终止条件
        if(root==nullptr) return root;    
        //3、确定单层循环逻辑
        swap(root->left,root->right);    //中
        invertTree(root->left);          //左
        invertTree(root->right);         //右
        return root;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 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* invertTree(TreeNode* root) {
      stack<TreeNode*> stk;
      if(root!=nullptr) stk.push(root);
      while(!stk.empty()){
         TreeNode *node=stk.top();  //取出栈顶元素
         if(node!=nullptr){
             stk.pop();      //将该节点弹出，避免重复操作
             if(node->right) stk.push(node->right); //右
             if(node->left) stk.push(node->left);   //左

             stk.push(node);                        //中  不是node->val
             stk.push(nullptr);
         }else{
             stk.pop();      //将空节点弹出
             node=stk.top(); //再次取出栈顶元素
             stk.pop();
             swap(node->left,node->right);    //交换左右节点
         }
      }
      return root;
    }
};

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(root==NULL) return root;
        swap(root->left,root->right);
        mirrorTree(root->left);
        mirrorTree(root->right);
        return root;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        queue<TreeNode*> que;
        if(root!=NULL) que.push(root);
        while(!que.empty()){
            int n=que.size();
            for(int i=0;i<n;++i){
                TreeNode *node=que.front();
                que.pop();
                swap(node->left,node->right);
                if(node->left)  que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return root;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 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:
    //递归三部曲：1、确定递归函数的参数和返回值
    bool compare(TreeNode* left,TreeNode *right){   
         //2、确定终止条件
         // 首先排除空节点的情况
        if (left == nullptr && right != nullptr) return false;
        else if (left != nullptr && right == nullptr) return false;
        else if (left == nullptr && right == nullptr) return true;
        // 排除了空节点，再排除数值不相同的情况
        else if (left->val != right->val) return false;
        // 此时就是：左右节点都不为空，且数值相同的情况，此时才做递归，做下一层的判断
        //3、确定单层递归逻辑
        else return compare(left->left, right->right) && compare(left->right, right->left);
        //等价于以下三行       
        //bool outside=compare(left->left,right->right);
        //bool inside=compare(left->right,right->left);
        //bool isSame=outside&&inside;        
    }
    bool isSymmetric(TreeNode* root) {
       if(root==nullptr) return true;
       return compare(root->left,root->right);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    //递归三部曲：1、确定递归函数的参数和返回值
    bool compare(TreeNode* left,TreeNode *right){   
        //2、确定终止条件
        if (left == nullptr && right == nullptr) return true;
        if (left == nullptr || right == nullptr) return false;
        //3、确定单层递归逻辑
        return left->val == right->val && compare(left->left, right->right) && compare(left->right, right->left);       
    }
    bool isSymmetric(TreeNode* root) {
      //if(root==nullptr) return true;
      return compare(root->left,root->right);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 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 isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;        
        queue<TreeNode*> que;
        que.push(root->left);   // 将左子树头结点加入队列
        que.push(root->right);  // 将右子树头结点加入队列        
        while (!que.empty()) {  // 接下来就要判断这两个树是否相互翻转
            TreeNode* leftNode = que.front(); que.pop();
            TreeNode* rightNode = que.front(); que.pop();
            if (!leftNode && !rightNode) {  // 左节点为空、右节点为空，此时说明是对称的
                continue;
            }

            // 左右一个节点不为空，或者都不为空但数值不相同，返回false
            if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
                return false;
            }
            que.push(leftNode->left);   // 加入左节点左孩子
            que.push(rightNode->right); // 加入右节点右孩子
            que.push(leftNode->right);  // 加入左节点右孩子
            que.push(rightNode->left);  // 加入右节点左孩子
        }
        return true;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool compare(TreeNode* left,TreeNode* right){
        if(!left && !right) return true;
        if(!left || !right) return false;
        return left->val==right->val && compare(left->left,right->right) && compare(left->right,right->left);
    }
    bool isSymmetric(TreeNode* root) {
        if(root==NULL) return true;
        return compare(root->left,root->right);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 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 isSameTree(TreeNode* p, TreeNode* q) {
      if(!p && !q) return true;
      else if(p==nullptr||q==nullptr) return false;
      //else if(p==nullptr && q!=nullptr) return false;
      //else if(p!=nullptr && q==nullptr) return false;
      else return p->val==q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * 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 isSameTree(TreeNode* p, TreeNode* q) {
      if (p==nullptr && q==nullptr) return true;     
        queue<TreeNode*> que;
        que.push(p);   // 将左根结点加入队列
        que.push(q);   // 将右根结点加入队列
        
        while (!que.empty()) {  // 接下来就要判断这两个树是否相同
            TreeNode* leftNode = que.front(); que.pop();
            TreeNode* rightNode = que.front(); que.pop();
            if (!leftNode && !rightNode) {  // 左节点为空、右节点为空，此时说明是对称的
                continue;
            }

            // 左右一个节点不为空，或者都不为空但数值不相同，返回false
            if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
                return false;
            }
            que.push(leftNode->left);    // 加入左节点左孩子
            que.push(rightNode->left);   // 加入右节点右孩子
            que.push(leftNode->right);   // 加入左节点右孩子
            que.push(rightNode->right);  // 加入右节点左孩子
        }
        return true;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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 check(TreeNode *s,TreeNode *t){
        if(!s && !t) return true;   //全空
        if(!s || !t) return false;
        return s->val == t->val && check(s->left,t->left) && check(s->right,t->right);
    }
    
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if(!root) return false;
        return check(root,subRoot) || isSubtree(root->left,subRoot) ||isSubtree(root->right,subRoot);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool check(TreeNode *s,TreeNode *t){
        if(!t) return true;   
        if(!s) return false;
        return s->val == t->val && check(s->left,t->left) && check(s->right,t->right);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!A || !B) return false;
        return check(A,B)||isSubStructure(A->left,B)||isSubStructure(A->right,B);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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:
    int countNodes(TreeNode* root) {
       if(root==nullptr) return 0;
       return 1+countNodes(root->left)+countNodes(root->right);//后序遍历
    }
};
/*int leftNum = getNodesNum(cur->left);      // 左
  int rightNum = getNodesNum(cur->right);    // 右
  int treeNum = leftNum + rightNum + 1;      // 中
  return treeNum; */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 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:
    int countNodes(TreeNode* root) {
      queue<TreeNode*> que;
      if(root!=nullptr) que.push(root);
      int ans=0;
      while(!que.empty()){
          int size=que.size();
          for(int i=0;i<size;++i){
              TreeNode *node=que.front();
              que.pop();
              ans++;   // 记录节点数量
              if(node->left) que.push(node->left);
              if(node->right) que.push(node->right);
          }
      }
      return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 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 {          //递归到某一深度一定会有左孩子或者右孩子为满二叉树，利用满二叉树的特性:节点数= 2^树深度 - 1 
public:
    int countNodes(TreeNode* root) {
        if(root==nullptr) return 0;
        int leftHeight=0,rightHeight=0; // 这里初始为0是有目的的，为了下面求指数方便
        TreeNode *left=root->left;
        TreeNode *right=root->right;

        //求左子树深度
        while(left){
            left=left->left;
            leftHeight++;
        }
        //求右子树深度
        while(right){
            right=right->right;
            rightHeight++;
        }
        if(leftHeight==rightHeight){   //找到满二叉树
            return (2<<leftHeight)-1;  // 注意(2<<1) 相当于2^2，所以leftHeight初始为0    
        }
       return 1+countNodes(root->left)+countNodes(root->right);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 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:        //后序遍历  左  右   中
    //1、确定递归函数的参数和返回值
    int sumOfLeftLeaves(TreeNode* root) {
        //2、确定终止条件
        if(root==nullptr) return 0;
        //3、确定单层递归的逻辑
        int leftSum=sumOfLeftLeaves(root->left);    //左
        int rightSum=sumOfLeftLeaves(root->right);  //右
        int midSum=0;                               //中
        if(root->left!=nullptr && root->left->left==nullptr && root->left->right==nullptr){//左叶子判断条件
            midSum=root->left->val;
        }  
        return leftSum+rightSum+midSum;
    }
};
/*int midSum=0;       简化                     
  if(root->left!=nullptr && root->left->left==nullptr && root->left->right==nullptr){//左叶子判断条件
        midSum=root->left->val;
  }  
  return sumOfLeftLeaves(root->left)+sumOfLeftLeaves(root->right)+midSum; */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 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:        //前序遍历   中  左  右
    int sumOfLeftLeaves(TreeNode* root) {
      if(root==nullptr) return 0;
      queue<TreeNode*> que;
      que.push(root);
      int sum=0;
      while(!que.empty()){
          int size=que.size();
          for(int i=0;i<size;++i){
              TreeNode *node=que.front();
              que.pop();
              if(node->left!=nullptr && node->left->left==nullptr && node->left->right==nullptr)   //左叶子判断条件
              sum+=node->left->val;             
              if(node->left)  que.push(node->left);
              if(node->right) que.push(node->right);
          }
      }
      return sum;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 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:
    int findBottomLeftValue(TreeNode* root) {
      if(root==nullptr) return 0;
      queue<TreeNode*> que;
      que.push(root);
      int ans;
      while(!que.empty()){
          int size=que.size();
          for(int i=0;i<size;++i){
              TreeNode *node=que.front();
              que.pop();
              
              if(i==0) ans=node->val;     //每层最左侧的元素
              
              if(node->left) que.push(node->left);
              if(node->right) que.push(node->right);
          }
      }
      return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * 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 {
private:
    //要传入根节点、记录每一条路径的path、和存放结果集的ans，这里递归不需要返回值
    void Traversal(TreeNode *node,vector<int> &path, vector<string> &ans){
        path.push_back(node->val);     //因为是前序遍历，需要先处理中间节点，中间节点就是我们要记录路径上的节点，先放进path中
        //然后是递归和回溯的过程
        if(node->left==nullptr && node->right==nullptr){  //终止处理逻辑
            string sPath;
            for(int i=0;i<path.size()-1;++i){       // 将path里记录的路径转为string格式
                sPath+=to_string(path[i]);
                sPath+="->";
            }
            sPath+=to_string(path[path.size()-1]);  // 记录最后一个节点（叶子节点）
            ans.push_back(sPath);                   // 收集一个路径
            return;
        }    
            
        //回溯和递归是一一对应的，有一个递归，就要有一个回溯
        if(node->left){
            Traversal(node->left,path,ans);
            path.pop_back();       //回溯
        }
        if(node->right){
            Traversal(node->right,path,ans);
            path.pop_back();       //回溯
        }
    }
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ans;
        vector<int> path;
        if(root==nullptr) return ans;
        Traversal(root,path,ans);
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//简化
class Solution {
private:
    //string path，每次都是复制赋值，不用使用引用，否则就无法做到回溯的效果
    void Paths(TreeNode* root, string path, vector<string>& ans) {
        if (root != nullptr) {
            path += to_string(root->val);        //中
            if (root->left == nullptr && root->right == nullptr) {  // 当前节点是叶子节点
                ans.push_back(path);                              // 把路径加入到答案中
            } else {
                path += "->";  // 当前节点不是叶子节点，继续递归遍历（隐藏了回溯）
                Paths(root->left, path, ans);    //左
                Paths(root->right, path, ans);   //右
            }
        }
    }
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ans;
        Paths(root, "", ans);
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 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:
     //1、确定递归函数的参数和返回类型
    bool traversal(TreeNode *node, int count){
        //2、递归终止条件代码
        if(node->left==nullptr && node->right==nullptr && count==0) return true;
        //3、确定单层递归的逻辑
        if(node->left){// 左（空节点不遍历）
            count-=node->left->val;   //递归，处理节点
            if(traversal(node->left,count)) return true;
            count+=node->left->val;   //回溯，撤销处理结果
        }
        if(node->right){// 右（空节点不遍历）
            if(traversal(node->right,count - node->right->val))  return true;   //隐藏回溯的逻辑
            //count-=node->right->val;
            //if(traversal(node->right,count)) return true;
            //count+=node->right->val;     
        }
        return false;
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root==nullptr) return false;
        return traversal(root,targetSum - root->val);
    }
};

1
2
3
4
5
6
7
8
class Solution {  //简化
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
      if(root==nullptr) return false;
      if(root->left==nullptr && root->right==nullptr && targetSum==root->val) return true;
      return hasPathSum(root->left,targetSum-root->val) || hasPathSum(root->right,targetSum-root->val);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 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;
       // 此时栈里要放的是pair<节点指针，路径数值>
       stack<pair<TreeNode*,int>> stk;
       stk.push(pair<TreeNode*,int>(root,root->val));

       while(!stk.empty()){
           pair<TreeNode*,int> node=stk.top();
           stk.pop();
           if(node.first->left==nullptr && node.first->right==nullptr && targetSum==node.second)  return true;

           //左节点，压进去一个节点的时候，将该节点的路径数值也记录下来
           if(node.first->left)  stk.push(pair<TreeNode*,int>(node.first->left,node.second+node.first->left->val));
           if(node.first->right) stk.push(pair<TreeNode*,int>(node.first->right,node.second+node.first->right->val));
       }
       return false;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 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 {
private:
     // 递归函数不需要返回值，因为我们要遍历整个树
     void traversal(TreeNode* node,int count){
         if(node->left==nullptr && node->right==nullptr && count==0){//找到叶子节点，且找到目标路径和
            ans.push_back(vec);
            return;
         }

         if(node->left){     //遍历左节点
             vec.push_back(node->left->val);
             count-=node->left->val;
             traversal(node->left,count);   //递归
             count+=node->left->val;        //回溯
             vec.pop_back();                //回溯
         }
         if(node->right){
             vec.push_back(node->right->val);
             traversal(node->right,count-=node->right->val); //隐藏回溯
             vec.pop_back();
         }
         return;
     }
     vector<vector<int>> ans;
     vector<int> vec;
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        //ans.clear();
        //vec.clear();
        if(root==nullptr) return ans;
        vec.push_back(root->val);    //把根节点放入路径
        traversal(root,targetSum-root->val);
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
private:
    void Traversal(TreeNode* node,int count){
        if(node->left==nullptr&&node->right==nullptr&&count==0){
            ans.push_back(path);return;
        }
        if(node->left){
            path.push_back(node->left->val);
            Traversal(node->left,count-node->left->val);
            path.pop_back();
        }
        if(node->right){
            path.push_back(node->right->val);
            Traversal(node->right,count-node->right->val);
            path.pop_back();
        }
        return;
    }
    vector<int> path;
    vector<vector<int>> ans;
public:
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        if(root==nullptr) return ans;
        path.push_back(root->val);
        Traversal(root,target-root->val);
        return ans; 
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * 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 {
private:
    //将数组转化为int
    int pathToInt(vector<int> &nums){
        int sum=0;
        for(int i=0;i<nums.size();++i){
            sum=sum*10+nums[i];
        }
        return sum;
    }
    void Traversal(TreeNode* node){
        if(!node->left && !node->right){  //终止条件是碰到叶子节点
            ans+=pathToInt(path);
            return;
        }
        if(node->left){// 左 （空节点不遍历）
            path.push_back(node->left->val); // 处理节点
            Traversal(node->left);           //递归
            path.pop_back();                  //回溯
        }
        if(node->right){
            path.push_back(node->right->val);
            Traversal(node->right);
            path.pop_back();
        }
    }
    int ans;
    vector<int> path;
public:
    int sumNumbers(TreeNode* root) {
        if(root==nullptr) return 0;
        path.push_back(root->val);
        Traversal(root);
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
private:
    int Traversal(TreeNode* node,int preSum){
        if(node==nullptr) return 0;
        int sum=preSum*10+node->val;
        if(!node->left && !node->right){  //终止条件是碰到叶子节点
            return sum;
        }else{
            return Traversal(node->left,sum)+Traversal(node->right,sum);
        }
    }
public:
    int sumNumbers(TreeNode* root) {
        return Traversal(root,0);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
private:
    //设置一个函数：返回该节点的最大贡献值
    int maxGain(TreeNode *node){
        if(node==nullptr) return 0;
        // 递归计算左右子节点的最大贡献值，并且只有在最大贡献值大于 0 时，才会选取对应子节点
        int left=max(0,maxGain(node->left));
        int right=max(0,maxGain(node->right));
        // 节点的最大路径和：取决于该节点的值与该节点的左右子节点的最大贡献值
        maxSum=max(maxSum,node->val + left + right);
        return node->val+max(left,right);   //最大贡献值：以该节点为根节点+左右子树最大的一个（只能选择一个）
    }
    int maxSum=INT_MIN;
public:
    int maxPathSum(TreeNode* root) {
        maxGain(root);
        return maxSum;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 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 {
private:
    int depth(TreeNode* root){
        if(root==nullptr){
            return 0;
        }
        int L=depth(root->left);   // 左儿子为根的子树的深度
        int R=depth(root->right);  // 右儿子为根的子树的深度
        ans=max(ans,L+R+1);        // 计算d_node即L+R+1 并更新ans
        return max(L,R)+1;      // 返回该节点为根的子树的深度
    }
    int ans=1;
public:
    int diameterOfBinaryTree(TreeNode* root) {
        depth(root);
        return ans-1;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 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* Traversal(vector<int>& preorder,vector<int>& inorder){
        if(preorder.size()==0) return nullptr;
        int rootValue=preorder[0];
        TreeNode* root= new TreeNode(rootValue);
        if(preorder.size()==1) return root;
        int index=0;
        for(;index<inorder.size();++index){
            if(inorder[index]==rootValue) break;
        }
        vector<int> leftInorder(inorder.begin(),inorder.begin()+index);
        vector<int> rightInorder(inorder.begin()+index+1,inorder.end());

        vector<int> leftPreorder(preorder.begin()+1,preorder.begin()+1+leftInorder.size());   //此处  +1  
        vector<int> rightPreorder(preorder.begin()+1+leftInorder.size(),preorder.end());
        root->left=Traversal(leftPreorder,leftInorder);
        root->right=Traversal(rightPreorder,rightInorder);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
       if(preorder.size()==0 || inorder.size()==0) return nullptr;
       return Traversal(preorder,inorder);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
private:
        TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& preorder, int preorderBegin, int preorderEnd) {
        if (preorderBegin == preorderEnd) return NULL;

        int rootValue = preorder[preorderBegin]; // 注意用preorderBegin 不要用0
        TreeNode* root = new TreeNode(rootValue);

        if (preorderEnd - preorderBegin == 1) return root;

        int delimiterIndex;
        for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }
        // 切割中序数组
        // 中序左区间，左闭右开[leftInorderBegin, leftInorderEnd)
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = delimiterIndex;
        // 中序右区间，左闭右开[rightInorderBegin, rightInorderEnd)
        int rightInorderBegin = delimiterIndex + 1;
        int rightInorderEnd = inorderEnd;

        // 切割前序数组
        // 前序左区间，左闭右开[leftPreorderBegin, leftPreorderEnd)
        int leftPreorderBegin =  preorderBegin + 1;
        int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin; // 终止位置是起始位置加上中序左区间的大小size
        // 前序右区间, 左闭右开[rightPreorderBegin, rightPreorderEnd)
        int rightPreorderBegin = preorderBegin + 1 + (delimiterIndex - inorderBegin);
        int rightPreorderEnd = preorderEnd;

        root->left = traversal(inorder, leftInorderBegin, leftInorderEnd,  preorder, leftPreorderBegin, leftPreorderEnd);
        root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, preorder, rightPreorderBegin, rightPreorderEnd);

        return root;
    }

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (inorder.size() == 0 || preorder.size() == 0) return nullptr;
        // 坚持左闭右开的原则
        return traversal(inorder, 0, inorder.size(), preorder, 0, preorder.size());
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 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* Traversal(vector<int> &inorder,vector<int> &postorder){
        if(postorder.size()==0) return nullptr;
       
        // 1、后序遍历数组最后一个元素，就是当前的中间节点
        int rootValue=postorder[postorder.size()-1];
        TreeNode *root=new TreeNode(rootValue);     //重点理解
        if(postorder.size()==1) return root;        //叶子节点
        // 2、找到中序遍历的切割点 
        int index=0;    //后面需要用到，必须单独设出
        for(;index < inorder.size();index++){       //此处如果是 int index=0; 就是错误
            if(inorder[index]==rootValue) break;
        }
        // 3、切割中序数组：坚持一致的左闭右开  左闭右开  左闭右开
        vector<int> leftInorder(inorder.begin(),inorder.begin()+index);
        vector<int> rightInorder(inorder.begin()+index+1,inorder.end());
        // 4、切割后序元素：同样坚持左闭右开
        //leftInorder.size()利用前序左数组，因为两个左右数组的个数一定是相等的
        postorder.resize(postorder.size()-1);       //postorder 丢弃已经用过的最后一个元素
        vector<int> leftPostorder(postorder.begin(),postorder.begin()+leftInorder.size());   
        vector<int> rightPostorder(postorder.begin()+leftInorder.size(),postorder.end());
        // 5、递归处理左区间和右区间
        //root->left = traversal(中序左数组, 后序左数组);
        //root->right = traversal(中序右数组, 后序右数组);
        root->left =Traversal(leftInorder,leftPostorder);
        root->right=Traversal(rightInorder,rightPostorder);       
        return root;
    }               
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
      if(inorder.size()==0 || postorder.size()==0) return nullptr;
      return Traversal(inorder,postorder);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {    //下表索引  因为原始的代码，每层递归定义了新的vector（就是数组），既耗时又耗空间，
private:
    // 中序区间：[inorderBegin, inorderEnd)，后序区间[postorderBegin, postorderEnd)
    TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd) {
        if (postorderBegin == postorderEnd) return nullptr;

        int rootValue = postorder[postorderEnd - 1];
        TreeNode* root = new TreeNode(rootValue);
        if (postorderEnd - postorderBegin == 1) return root;
        // 找到中序遍历的切割点
        int index;
        for (index = inorderBegin; index < inorderEnd; index++) {
            if (inorder[index] == rootValue) break;
        }
        // 切割中序数组
        // 左中序区间，左闭右开[leftInorderBegin, leftInorderEnd)
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = index;
        // 右中序区间，左闭右开[rightInorderBegin, rightInorderEnd)
        int rightInorderBegin = index + 1;
        int rightInorderEnd = inorderEnd;

        // 切割后序数组
        // 左后序区间，左闭右开[leftPostorderBegin, leftPostorderEnd)
        int leftPostorderBegin =  postorderBegin;
        int leftPostorderEnd = postorderBegin + index - inorderBegin; // 终止位置是 需要加上 中序区间的大小size
        // 右后序区间，左闭右开[rightPostorderBegin, rightPostorderEnd)
        int rightPostorderBegin = postorderBegin + (index - inorderBegin);
        int rightPostorderEnd = postorderEnd - 1; // 排除最后一个元素，已经作为节点了

        root->left = traversal(inorder, leftInorderBegin, leftInorderEnd,  postorder, leftPostorderBegin, leftPostorderEnd);
        root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, postorder, rightPostorderBegin, rightPostorderEnd);

        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        // 左闭右开的原则
        return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 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* constructMaximumBinaryTree(vector<int>& nums) {
        //当递归遍历的时候，如果传入的数组大小为1，说明遍历到了叶子节点了
        //定义一个新的节点，并把这个数组的数值赋给新的节点，然后返回这个节点。 这表示一个数组大小是1的时候，构造了一个新的节点，并返回。  
        TreeNode *node=new TreeNode(0);
        if(nums.size()==1){
            node->val=nums[0];
            return node;
        }
        //找到数组中最大的值和下标    有能力可考虑哈希
        int maxValue=0,maxValueIndex=0;
        for(int i=0;i<nums.size();++i){
            if(nums[i]>maxValue){
                maxValue=nums[i];
                maxValueIndex=i;
            }
        }        
        node->val=maxValue;  //根节点
        //构造左子树
        if(maxValueIndex>0){   //保证左区间至少有一个数值
            vector<int> newVec(nums.begin(),nums.begin()+maxValueIndex);
            node->left=constructMaximumBinaryTree(newVec);
        }
        //构造右子树
        if(maxValueIndex<nums.size()-1){   //确保右区间至少有一个数值
            vector<int> newVec(nums.begin()+maxValueIndex+1,nums.end());
            node->right=constructMaximumBinaryTree(newVec);
        }
        return node;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {    //每次分隔不用定义新的数组，而是通过下表索引直接在原数组上操作
public:
    TreeNode* Traversal(vector<int> &nums,int left,int right){
        if(left>=right) return nullptr;
        //分割点
        int maxValueIndex=left;
        for(int i=left+1;i<right;++i){
            if(nums[i]>nums[maxValueIndex]) maxValueIndex=i;
        }
        TreeNode* root=new TreeNode(nums[maxValueIndex]);    //重点理解
        //允许空节点进入递归，所以不用在递归的时候加判断节点是否为空
        // 左闭右开：[left, maxValueIndex)
        root->left=Traversal(nums,left,maxValueIndex);
        // 左闭右开：[maxValueIndex + 1, right)
        root->right=Traversal(nums,maxValueIndex+1,right);
        return root;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
       return Traversal(nums,0,nums.size());
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 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:
    // 1、确定递归函数的参数和返回值：
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        //2、确定终止条件
        if(root1==nullptr) return root2;
        if(root2==nullptr) return root1;
        //3、确定单层递归逻辑
        // 修改了t1的数值和结构
        root1->val+=root2->val;                            //中
        root1->left=mergeTrees(root1->left,root2->left);   //左
        root1->right=mergeTrees(root1->right,root2->right);//右
        return root1;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * 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* mergeTrees(TreeNode* root1, TreeNode* root2) {
      if(root1==nullptr) return root2;
      if(root2==nullptr) return root1;
      queue<TreeNode*> que;
      que.push(root1);
      que.push(root2);
      while(!que.empty()){
          TreeNode* node1=que.front();  que.pop();
          TreeNode* node2=que.front();  que.pop();
          // 此时两个节点一定不为空，val相加
          node1->val+=node2->val;
          //如果两颗子树的左、右节点都不为空，加入队列
          if(node1->left!=nullptr && node2->left!=nullptr){
              que.push(node1->left);
              que.push(node2->left);
          }
          if(node1->right != nullptr && node2->right!=nullptr){
               que.push(node1->right);
               que.push(node2->right);
          }
          //如果1的左右节点为空，2不为空，就赋值过去
          if(node1->left==nullptr && node2->left!=nullptr)   node1->left=node2->left;
          if(node1->right==nullptr && node2->right!=nullptr)  node1->right=node2->right;
       }
       return root1;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 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 {       //递归： 中序遍历是递增数组
private:
    void Traversal(TreeNode* root){
        if(root==nullptr) return;     
        Traversal(root->left);
        vec.push_back(root->val);    //将二叉搜索树转化为数组
        Traversal(root->right);
    }
    vector<int> vec;
public:
    bool isValidBST(TreeNode* root) {
        //vec.clear();
        Traversal(root);
        for(int i=1;i<vec.size();++i){    //注意此处要从1开始
            // 注意要小于等于，搜索树里不能有相同元素
            if(vec[i]<=vec[i-1]) return false;
        }
        return true;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 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 isValidBST(TreeNode* root) {
       stack<TreeNode*> stk;
       TreeNode* node=root;
       TreeNode* pre=nullptr;    //哨兵节点，记录前一个元素

       while(node!=nullptr || !stk.empty()){
           if(node!=nullptr){
               stk.push(node);
               node=node->left;
           }else{
               node=stk.top();   //取出栈顶元素
               stk.pop();
               if(pre!=nullptr && pre->val>=node->val)  return false;
               pre=node;        //保持前一个访问节点

               node=node->right;
           }
       }
       return true;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 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* searchBST(TreeNode* root, int target) {
       if(root==nullptr || root->val==target) return root;
       return  searchBST(root->val > target ? root->left : root->right,target);
       //因为搜索到目标节点了，就要立即return，这样才是找到节点就返回（搜索某一条边），如果不加return，就是遍历整棵树了
       //if(root->val > target)  return searchBST(root->left,target);  //搜索左子树 
       //if(root->val < target)  return searchBST(root->right,target); //搜索右子树
       //return root;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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* searchBST(TreeNode* root, int target) {
      while(root!=nullptr){
          if(target == root->val)  return root;
          root = root->val > target ? root->left : root->right;
          // if(root->val > target)  root=root->left;
          //else if(root->val<target)  root=root->right;
          //else return root;
      }
      return nullptr;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 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 {
private:
    void traversal(TreeNode* cur) {
        if (cur == nullptr) return;
        traversal(cur->left);   // 左
        if (pre != nullptr){    // 中
            ans = min(ans, cur->val - pre->val);
        }
        pre = cur; // 记录前一个
        traversal(cur->right);  // 右
    }
    int ans = INT_MAX;
    TreeNode  *pre;
public:
    int getMinimumDifference(TreeNode* root) {
        traversal(root);
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * 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:
    int getMinimumDifference(TreeNode* root) {
      stack<TreeNode*> stk;
      TreeNode* node=root;
      TreeNode* pre=nullptr;
      int ans=INT_MAX;
      while(node!=nullptr || !stk.empty()){
          if(node!=nullptr) {
              stk.push(node);   //指针访问节点，访问到最底层，将访问的节点放入栈中
              node=node->left;
          }else{
             node=stk.top();
             stk.pop();
             if(pre!=nullptr)  ans=min(ans,node->val - pre->val);
             pre=node;

             node=node->right;
          }
      }
      return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 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:
    // map<int, int>    key:元素，value:出现频率
    void searchBST(TreeNode* node,unordered_map<int,int>& map){
        //前序
        if(node==nullptr) return;
        map[node->val]++;    //统计元素频率
        searchBST(node->left,map);
        searchBST(node->right,map);
        return;
    }
   
    bool static cmp(const pair<int,int>& a,const pair<int,int>& b)  {return a.second>b.second;}  // 按照频率从大到小排序

    vector<int> findMode(TreeNode* root) {
        unordered_map<int,int> map;
        vector<int> ans;
        if(root==nullptr) return ans;
        searchBST(root,map);

        //把map转化数组即vector，再进行排序，当然vector里面放的也是pair<int, int>类型的数据，第一个int为元素，第二个int为出现频率
        vector<pair<int,int>>  vec(map.begin(),map.end());
        sort(vec.begin(),vec.end(),cmp);   //给出现的频率排序

        //将出现频率最高的元素放在ans中
        ans.push_back(vec[0].first);
        for(int i=1;i<vec.size();i++){    //i必须从1开始
           if(vec[i].second==vec[0].second)  ans.push_back(vec[i].first);     //必须是  .second  ，将出现次数相同的都放入数组中
           else break;
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 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:
    int maxCount,count;
    TreeNode* pre;
    vector<int> ans;
    
    void searchBST(TreeNode* node){
        if(node==nullptr) return;
        searchBST(node->left);   //左
        //中
        if(pre==nullptr){count=1;}
        else if(pre->val==node->val){count++;}   //与前一个节点相同，需要统计频率+1
        else{count=1;}
        pre=node;  //更新上一个节点

        if(count==maxCount){ans.push_back(node->val);}  //和最大值相同，放入数组中
        if(count>maxCount){
            maxCount=count;
            ans.clear();    //更新最大频率后，需要将ans的数组清空，之前的元素全部失效
            ans.push_back(node->val);
        }
        searchBST(node->right);   //右
        return;
    }

    vector<int> findMode(TreeNode* root) {
       count=0;maxCount=0;
       TreeNode* pre=nullptr;  //记录前一个节点
       ans.clear();
       searchBST(root);
       return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * 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> findMode(TreeNode* root) {
        int maxCount,count;
        vector<int> ans;
       stack<TreeNode*> stk;
       TreeNode* node=root;
       TreeNode* pre=nullptr;

       while(node!=nullptr || !stk.empty()){
           if(node!=nullptr){
               stk.push(node);  //指针访问节点，将访问的节点放入栈中
               node=node->left;
           }
           else{
               node=stk.top();stk.pop();
               
               if(pre==nullptr){count=1;}
               else if(pre->val==node->val){count++;}
               else{count=1;}

               if(count==maxCount){ans.push_back(node->val);}
               if(count>maxCount){
                   maxCount=count;
                   ans.clear();
                   ans.push_back(node->val);
               }
               pre=node;
               node=node->right;
           }
       }
       return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 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:         
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==p || root==q || root==NULL) return root;
        //单层递归逻辑
        TreeNode* left=lowestCommonAncestor(root->left,p,q);
        TreeNode* right=lowestCommonAncestor(root->right,p,q);

        //对left和right进行逻辑处理
        //如果left 和 right都不为空，说明此时root就是最近公共节点。这个比较好理解
        //如果left为空，right不为空，就返回right，说明目标节点是通过right返回的，反之依然
        if(left!=NULL && right!=NULL) return  root;
        if(right==NULL) return  left;
        return right;
        //if(left!=NULL && right==NULL) return  left;
        //if(left==NULL && right!=NULL) return  right;
        //else return NULL;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==p||root==q||root==NULL) return root;
        TreeNode* L=lowestCommonAncestor(root->left,p,q);
        TreeNode* R=lowestCommonAncestor(root->right,p,q);
        if(L!=NULL && R!=NULL) return root;
        if(L!=NULL){
            return L;
        }else{
            return R;
        }
        
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 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:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //if(root==NULL) return root;
        if(root->val > p->val && root->val > q->val){
             return lowestCommonAncestor(root->left,p,q);
         }else if(root->val < p->val && root->val < q->val){
            return lowestCommonAncestor(root->right,p,q);
        } 
        return root;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 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:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while(root){
            if(root->val > p->val && root->val > q->val) {root=root->left;}
            else if(root->val < p->val && root->val < q->val) {root=root->right;}
            else return root;
        }
        return NULL;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root->val>p->val && root->val>q->val){
            return lowestCommonAncestor(root->left,p,q); 
        }else if(root->val<p->val && root->val<q->val){
            return lowestCommonAncestor(root->right,p,q);
        }else{
            return root;
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while(root){
            if(root->val>p->val && root->val>q->val){
                root=root->left;
            }else if(root->val<p->val && root->val<q->val){
                root=root->right;
            }else{
                return root;
            }
        }
        return NULL;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 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 target) {
      //终止条件就是找到遍历的节点为null的时候，就是要插入节点的位置了，并把插入的节点返回
      if(root==nullptr){
           return new TreeNode(target);
           //TreeNode* node=new TreeNode(target);
           //return node;
      }
      //通过递归函数返回值完成了新加入节点的父子关系赋值操作，下一层将加入节点返回，本层用root->left或者root->right将其接住。
      if(root->val > target)  root->left = insertIntoBST(root->left,target);
      if(root->val < target)  root->right= insertIntoBST(root->right,target);
      return root;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 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 target) {
      //终止条件就是找到遍历的节点为null的时候，就是要插入节点的位置了，并把插入的节点返回
      if(root==nullptr){
          return new TreeNode(target);
          // TreeNode* node=new TreeNode(target);
          // return node;
      }

      TreeNode* node=root;
      TreeNode* parent=nullptr;   // 这个很重要，需要记录上一个节点，否则无法赋值新节点
      while(node!=nullptr){
          parent=node;
          if(node->val > target) node=node->left;
          else node=node->right;
      }

      //下面的迭代目的是把数值插入
      TreeNode* cur=new TreeNode(target);
      if(parent->val > target) parent->left=cur;      // 此时是用parent节点的进行赋值
      else parent->right=cur;
      return root;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * 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* deleteNode(TreeNode* root, int key) {
            // 第一种情况：没找到删除的节点，遍历到空节点直接返回了
       if(root==nullptr) return root;
       if(root->val > key) root->left=deleteNode(root->left,key);
       if(root->val < key) root->right=deleteNode(root->right,key);
       if(root->val ==key){
            // 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回nullptr为根节点
            if(root->left==nullptr && root->right==nullptr){
                  delete root;    //释放内存
                  return nullptr;
             }
            // 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
             else if(root->left==nullptr){
                 auto rootNode=root->right;
                 delete root;
                 return rootNode;
             }  
             // 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
             else if(root->right==nullptr){
                 auto rootNode=root->left;
                 delete root;
                 return rootNode;
             }
             // 第五种情况：左右孩子节点都不为空，则将 删除节点的左子树 放到 删除节点的右子树的最左面节点 的左孩子 的位置
             // 并返回删除节点右孩子为新的根节点。
             else{
                 // 找右子树最左面的节点
                 TreeNode* node=root->right;       //右子树
                 while(node->left!=nullptr) { node=node->left;}

                 node->left=root->left;            // 把要删除的节点（root）左子树放在node的左孩子的后面

                 //TreeNode* tmp=root;              //为了释放内存做准备
                 root=root->right;                // 返回旧root的右孩子作为新root
                 //delete tmp;
                 return root;
             }
       } 
       return root;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 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* trimBST(TreeNode* root, int low, int high) {
        if(root==nullptr) return nullptr;
        // 寻找符合区间[low, high]的节点
        if(root->val < low) return trimBST(root->right,low,high);
        if(root->val > high) return trimBST(root->left,low,high);
      
        root->left=trimBST(root->left,low,high);   // root->left接入符合条件的左孩子（将下一层处理完左子树的结果赋给root->left）
        root->right=trimBST(root->right,low,high); // root->right接入符合条件的右孩子
        return root;
    }
};
//if(root->val < low) return trimBST(root->right,low,high);
//root->left=trimBST(root->left,low,high);
//两步组合相当于 将不符合条件的节点删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * 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* trimBST(TreeNode* root, int low, int high) {
       if(!root)   return nullptr;
       //  1、 处理头结点，让root移动到[L, R] 范围内，注意是左闭右闭
       while(root!=nullptr && (root->val<low || root->val>high)){
           if(root->val < low) {root=root->right;}
           else root=root->left;
       }

       TreeNode* node=root;
       // 2、此时root已经在[L, R] 范围内，处理左孩子元素小于L的情况
       while(node!=nullptr){
           while(node->left && node->left->val < low){
               node->left=node->left->right;
           }
           node=node->left;
       }

       node=root;
       // 此时root已经在[L, R] 范围内，处理右孩子大于R的情况
       while(node!=nullptr){
           while(node->right && node->right->val > high){
               node->right=node->right->left;
           }
           node=node->right;
       }
       return root;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 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* Traversal(vector<int>& nums,int left,int right){
        if(left>right) return nullptr;

        int mid=left+(right-left)/2;    
        TreeNode* root=new TreeNode(nums[mid]);   //取了中间位置，就开始以中间位置的元素构造节点

        root->left=Traversal(nums,left,mid-1);    //构建左子树
        root->right=Traversal(nums,mid+1,right);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
      return Traversal(nums,0,nums.size()-1);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 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 {
private:
    //将二叉搜索树转化为有序数组：中序遍历
    void traversal(TreeNode* node){
        if(node==nullptr) return;
        traversal(node->left);
        vec.push_back(node->val);
        traversal(node->right);
    }
    //将有序数组转化为平衡二叉树
    TreeNode* getTree(vector<int>& nums,int left,int right){
        if(left>right) return nullptr;  //终止条件
        int mid=(right-left)/2+left; 
        TreeNode* root=new TreeNode(nums[mid]);
        root->left=getTree(nums,left,mid-1);
        root->right=getTree(nums,mid+1,right);
        return root;
    }
    vector<int> vec;
public:
    TreeNode* balanceBST(TreeNode* root) {
        traversal(root);
        return getTree(vec,0,vec.size()-1);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 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 {   //递归： 反中序遍历（右中左）  依次相加
private:
     void Traversal(TreeNode* root){  //不需要有返回值
        if(root==nullptr) return;
        Traversal(root->right);
        root->val += pre;
        pre=root->val;
        Traversal(root->left);
     }
     int pre=0;  //用于记录root前的数值
public:
    TreeNode* convertBST(TreeNode* root) {        
        Traversal(root);
        return root;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
private:
    int sum = 0;
public:
    TreeNode* convertBST(TreeNode* root) {
        if (root != nullptr) {
            convertBST(root->right);
            sum += root->val;
            root->val = sum;
            convertBST(root->left);
        }
        return root;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 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* convertBST(TreeNode* root) {
        stack<TreeNode*> stk;
        if(root!=nullptr) stk.push(root);
        int sum=0;
        while(!stk.empty()){
            TreeNode *node=stk.top();
            if(node!=nullptr){
                stk.pop();
                if(node->left) stk.push(node->left);    //左
                stk.push(node);                         //中
                stk.push(nullptr);
                if(node->right) stk.push(node->right);  //右
            }else{
                stk.pop();
                node=stk.top();   
                stk.pop();

                sum+=node->val;
                node->val=sum; 
            }
        }
        return root;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
private:
    void Traversal(TreeNode* root, int& k){ //必须加 & 不然错误
        if(root==NULL) return;
        Traversal(root->right,k);
        if(--k==0) ans=root->val;
        Traversal(root->left,k);
    }
    int ans;
public:
    int kthLargest(TreeNode* root, int k) {
        Traversal(root,k);
        return ans;       
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 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 {   //递归实现前序遍历
private:
    void Traversal(TreeNode* root,vector<TreeNode*> &vec){
        if(root!=nullptr){
            vec.push_back(root);
            Traversal(root->left,vec);
            Traversal(root->right,vec);
        }
    }
public:
    void flatten(TreeNode* root) {
        vector<TreeNode*> vec;
        Traversal(root,vec);
        for(int i=1;i<vec.size();++i){
            TreeNode *prev=vec[i-1], *cur=vec[i];
            prev->left=nullptr;
            prev->right=cur;
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode *cur=root;
        while(cur!=nullptr){
            //如果当前节点的左子节点不为空，则需要找到左子树中最下方最右边的节点，作为当前节点的右子节点的根节点
            if(cur->left!=nullptr){
                TreeNode *next=cur->left;
                TreeNode *pre=next;
                while(pre->right!=nullptr){   //寻找左子树中最下方最右边的节点（前驱节点）
                    pre=pre->right;
                }
                //作为当前节点的右子节点的根节点
                pre->right=cur->right;
                //为下一次循环做准备
                cur->left=nullptr;
                cur->right=next;
            }
            cur=cur->right;    //如果当前节点的左子节点为空，则该节点不需要进行展开操作。
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node() {}
    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }
    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};*/
class Solution {
private:
    void Traversal(Node* node){
        if(node==NULL) return;
        Traversal(node->left);
        if(tail!=NULL){//tail相当于前驱节点，node相当于当前节点
            tail->right=node;
            node->left=tail;
        }else{//代表正在访问链表头节点，记为 head ；
            head=node;
        }
        tail=node;  //更新 tail = node ，即节点 node 是后继节点的 tail 
        Traversal(node->right);
    }
    Node *head,*tail;
public:
    Node* treeToDoublyList(Node* root) {
        if(root==NULL) return NULL;
        Traversal(root); //中序遍历
        head->left=tail;
        tail->right=head;
        return head;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * }; */
class Codec {   //深度优先搜索：前序遍历
private:
    void rserialize(TreeNode *root,string &str){
        if(root==NULL){
            str+="null,";
        }else{
            str+=to_string(root->val)+",";  //to_string 将数字转化为字符类型
            rserialize(root->left,str);
            rserialize(root->right,str);
        }
    }

    TreeNode *rdeserialize(list<string>& data){
        if(data.front()=="null"){  //获取字符串第一个字符
            data.erase(data.begin());    //删除第一个元素：erase()返回值是删除元素的下一个迭代位置
            return NULL;                 //删除最后一个元素：data.pop_back();
        }
        //不为空：先解析这棵树的左子树，再解析它的右子树
        TreeNode *root=new TreeNode(stoi(data.front()));  //stoi()的参数是const string，作用是把数字字符串转换成int输出
        data.erase(data.begin());
        root->left=rdeserialize(data);
        root->right=rdeserialize(data);
        return root;
    }
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string str;
        rserialize(root,str);
        return str;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        list<string> dataList;
        string str;
        for(auto &ch:data){
            //首先我们需要根据 , 把原先的序列分割开来得到先序遍历的元素列表，然后从左向右遍历这个序列
            if(ch==','){
                dataList.push_back(str);
                str.clear();
            }else{
                str.push_back(ch);
            }
        }  
        if(!str.empty()){
            dataList.push_back(str);
            str.clear();
        }
        return rdeserialize(dataList);
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Codec {   //深度优先搜索：前序遍历
private:
    void rserialize(TreeNode *root,string &str){
        if(root==NULL){
            str+="null,";
        }else{
            str+=to_string(root->val)+",";  //to_string 将数字转化为字符类型
            rserialize(root->left,str);
            rserialize(root->right,str);
        }
    }

    TreeNode *rdeserialize(list<string>& data){
        if(data.front()=="null"){  //获取字符串第一个字符
            data.erase(data.begin());    //删除第一个元素：erase()返回值是删除元素的下一个迭代位置
            return NULL;                 //删除最后一个元素：data.pop_back();
        }
        //不为空：先解析这棵树的左子树，再解析它的右子树
        TreeNode *root=new TreeNode(stoi(data.front()));  //stoi()的参数是const string，作用是把数字字符串转换成int输出
        data.erase(data.begin());
        root->left=rdeserialize(data);
        root->right=rdeserialize(data);
        return root;
    }
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string str;
        rserialize(root,str);
        return str;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        list<string> dataList;
        string str;
        for(auto &ch:data){
            //首先我们需要根据 , 把原先的序列分割开来得到先序遍历的元素列表，然后从左向右遍历这个序列
            if(ch==','){
                dataList.push_back(str);
                str.clear();
            }else{
                str.push_back(ch);
            }
        }  
        if(!str.empty()){
            dataList.push_back(str);
            str.clear();
        }
        return rdeserialize(dataList);
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

1
2
3
4
5
6
7
8
9
10
11
void backTracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backTracking(路径，选择列表);   // 递归
        回溯，撤销处理结果 
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
private:
    void backTracking(int n,int k,int startIndex){//每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex。
        if(path.size()==k){
            ans.push_back(path);     //存放结果;
            return;
        }
        for(int i=startIndex;i<=n;++i){ // 控制树的横向遍历
            path.push_back(i);          // 处理节点 
            backTracking(n,k,i+1);      // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
            path.pop_back();            // 回溯，撤销处理的节点
        }
    }
    vector<int> path;
    vector<vector<int>> ans;
public:
    vector<vector<int>> combine(int n, int k) {
       //path.clear();
       //ans.clear(); 
       backTracking(n,k,1);
       return ans;
    }
};

1
2
3
4
5
//已经选择的元素个数：path.size();
//还需要的元素个数为: k - path.size();
//在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++)  //注意+1，保持左闭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
private:
    //首先使用哈希表存储每个数字对应的所有可能的字母，然后进行回溯操作
    unordered_map<char, string> phoneMap{
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };

    //index是记录遍历第几个数字了，就是用来遍历digits（数字字符串），同时index也表示树的深度。
    void backTracking(const string& digits,int index){
        if(digits.size()==index){
            ans.push_back(s);
            return;
        }
  
        //取出哈希表中数字所对应的字符集
        char digit=digits[index];
        string letters=phoneMap.at(digit);

        for(int i=0;i<letters.size();++i){
            s.push_back(letters[i]);
            backTracking(digits,index+1);
            s.pop_back();
        }
    }
    vector<string> ans;
    string s;
public:
    vector<string> letterCombinations(string digits) {
       //s.clear();
       //ans.clear();
       if(digits.empty()){return ans;}
       backTracking(digits,0);
       return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
private:
    void backTracking(vector<int>& candidates,int target,int sum,int startIndex){
        if(sum>target){return;}
        if(sum==target){
            ans.push_back(path);
            return;
        }
        //本题元素是可以重复选择的
        for(int i=startIndex;i<candidates.size();++i){
            sum+=candidates[i];
            path.push_back(candidates[i]);
            backTracking(candidates,target,sum,i);      // 关键点:不用i+1了，表示可以重复读取当前的数
            sum-=candidates[i];
            path.pop_back();
        }
    }
    vector<int>path;
    vector<vector<int>> ans;

public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
      //path.clear();
      //ans.clear();
      backTracking(candidates,target,0,0);
      return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
private:
    void backTracking(vector<int>& candidates,int target,int sum,int startIndex){
        //if(sum>target){return;}
        if(sum==target){
            ans.push_back(path);
            return;
        }
        //本题元素是可以重复选择的
        // 如果 sum + candidates[i] > target 就终止遍历（优化，需要排序）
        for(int i=startIndex;i<candidates.size()  &&  (sum+candidates[i])<=target;++i){
            sum+=candidates[i];
            path.push_back(candidates[i]);
            backTracking(candidates,target,sum,i);      // 关键点:不用i+1了，表示可以重复读取当前的数
            sum-=candidates[i];
            path.pop_back();
        }
    }
    vector<int>path;
    vector<vector<int>> ans;

public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {;
      sort(candidates.begin(),candidates.end());   //需要排序
      backTracking(candidates,target,0,0);
      return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
private:
    //去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。
    void backTracking(vector<int>& candidates,int target,int sum,int startIndex){
       if(sum==target){
           ans.push_back(path);
           return;
       }
       //单层搜索的逻辑
       for(int i=startIndex;i<candidates.size() && sum+candidates[i]<=target;++i){
           // 要对同一树层使用过的元素进行跳过   i>startIndex
           if(i>startIndex && candidates[i]==candidates[i-1]){continue;}

           sum+=candidates[i];
           path.push_back(candidates[i]);          
           backTracking(candidates,target,sum,i+1);// 和39.组合总和区别:这里是i+1，每个数字在每个组合中只能使用一次       
           sum-=candidates[i];
           path.pop_back();      
       }
    }
    vector<int> path;
    vector<vector<int>> ans;
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
      //path.clear();
      //ans.clear();
      sort(candidates.begin(),candidates.end());  // 首先把给candidates排序，让其相同的元素都挨在一起。
      backTracking(candidates,target,0,0);
      return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
private:
    //bool型数组used，用来记录同一树枝上的元素是否使用过，担负去重的重任
    //去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。
    void backTracking(vector<int>& candidates,int target,int sum,int startIndex,vector<bool>& used){
       if(sum==target){
           ans.push_back(path);
           return;
       }
       //单层搜索的逻辑
       for(int i=startIndex;i<candidates.size() && sum+candidates[i]<=target;++i){
           //在candidates[i] == candidates[i - 1]相同的情况下：
           // used[i - 1] == true， 说明同一树枝candidates[i - 1]使用过
           // used[i - 1] == false，说明同一树层candidates[i - 1]使用过

           // 要对同一树层使用过的元素进行跳过
           if(i>0 && candidates[i]==candidates[i-1] && used[i-1]==false){continue;}

           sum+=candidates[i];
           path.push_back(candidates[i]);
           used[i]=true;
           backTracking(candidates,target,sum,i+1,used);// 和39.组合总和区别:这里是i+1，每个数字在每个组合中只能使用一次
           used[i]=false;
           sum-=candidates[i];
           path.pop_back();      
       }
    }
    vector<int> path;
    vector<vector<int>> ans;
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
      vector<bool> used(candidates.size(),false);   
      sort(candidates.begin(),candidates.end());  // 首先把给candidates排序，让其相同的元素都挨在一起。
      backTracking(candidates,target,0,0,used);
      return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
private:
    void backTracking(int k,int n,int sum,int startIndex){
        if(path.size()==k){  //数量要求体现在这里
            // sum：已经收集的元素的总和，也就是path里元素的总和。
            if(sum==n) ans.push_back(path);
            return;       // 如果path.size() == k 但sum != targetSum 直接返回
        }
        //处理过程 和 回溯过程是一一对应的，处理有加，回溯就要有减
        for(int i=startIndex;i<=9;++i){
            sum+=i;
            path.push_back(i);
            backTracking(k,n,sum,i+1);  // i+1表示不能重复
            sum-=i;
            path.pop_back();
        }
    }
    vector<int>path;
    vector<vector<int>> ans;
public:
    vector<vector<int>> combinationSum3(int k, int n) {
      //path.clear();
      //ans.clear();
      backTracking(k,n,0,1);
      return ans;
    }
};

1
for(int i=startIndex;i<=9 && sum<n;++i)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
private:
        //判断是不是回文串,利用双指针
        bool isPartition(const string& s,int start,int end){
           for(int i=start,j=end;i<j;++i,--j){
               if(s[i]!=s[j]){
                   return false;
               } 
           }
           return true;
        }

     void backTracking(const string& s,int startIndex){
        // 如果起始位置已经大于s的大小，说明已经找到了一组分割方案
        if(startIndex>=s.size()){
            ans.push_back(path);
            return;
        }
        
        for(int i=startIndex;i<s.size();++i){  //起始位置startIndex，那么 [startIndex, i] 就是要截取的子串
           if(isPartition(s,startIndex,i)){
               // 获取[startIndex,i]在s中的子串
               string str=s.substr(startIndex,i-startIndex+1) ;   //从下标为 startIndex 的位置开始,拷贝 i-startIndex+1 个字符返回
               path.push_back(str);
           }else{continue;}
           backTracking(s,i+1); // 寻找i+1为起始位置的子串（不重复使用）
           path.pop_back();     // 回溯过程，弹出本次已经填在的子串         
        }
    }
    vector<string> path;
    vector<vector<string>> ans;
public:
    vector<vector<string>> partition(string s) {
       //path.clear();
       //ans.clear();
       backTracking(s,0);
       return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
private:
     //判断子串是否合法  ,  左闭右闭[start,end]
     bool isValid(const string& s,int start,int end){
         if(start>end){return false;}
         //1、0开头的数字,不合法
         if(s[start]=='0' && start!=end){return false;}     //s[start]==0 是错误代码
         int num=0;
         for(int i=start;i<=end;i++){
             //2、遇到非数字字符,不合法
             //if(s[i]<'0' || s[i]>'9'){return false;}     
             //3、如果大于255,不合法
             num=num*10+(s[i]-'0');    //(s[i]-'0') 字符转化为数字
             if(num>255){return false;}
         }
         return true;
     }
     // startIndex: 搜索的起始位置，pointNum:添加小数点的数量
    void backTracking(string& s,int startIndex,int pointNum){//此处不能定义为 const string& s
        if(pointNum==3){   // 小数点数量为3时，分隔结束
            // 判断第四段子字符串是否合法，如果合法就放进result中
            if(isValid(s,startIndex,s.size()-1)){   //因为是左闭右闭的区间，所以用 s.size()-1
                ans.push_back(s);
            }
            return;
        }
        for(int i=startIndex;i<s.size();++i){
           // 判断 [startIndex,i] 这个区间的子串是否合法
           if(isValid(s,startIndex,i)){
               s.insert(s.begin()+i+1,'.');   // 在i+1的位置，即i的后面插入一个小数点
               pointNum++;
               backTracking(s,i+2,pointNum);  //考虑到插入小数点，故下一个字符串的起始位置是i+2
               pointNum--;
               s.erase(s.begin()+i+1);        //回溯删除小数点
           }else{break;}    // 不合法，直接结束本层循环
        }
    }
    vector<string> ans;
public:
    vector<string> restoreIpAddresses(string s) {
       //ans.clear();
       //if(s.size()>12) return ans;
       backTracking(s,0,0);
       return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
private:
    void backTracking(vector<int>& nums,int startIndex){
        ans.push_back(path);            // 收集子集，要放在终止添加的上面，否则会漏掉自己
        // if(startIndex>=nums.size()){return;}   终止条件可以不加，因为本层for循环本来也结束了
        for(int i=startIndex;i<nums.size();++i){
            path.push_back(nums[i]);    // 子集收集元素
            backTracking(nums,i+1);     // 注意从i+1开始，元素不重复取
            path.pop_back();            // 回溯
        }
    }   
    vector<int> path;
    vector<vector<int>> ans;
public:
    vector<vector<int>> subsets(vector<int>& nums) {
     //path.clear();
     //ans.clear();
     backTracking(nums,0);
     return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
private:
    void backTracking(vector<int>& nums,int startIndex){
        ans.push_back(path);
        unordered_set<int> set;  //利用set去重
        for(int i=startIndex;i<nums.size();++i){
            if(i>startIndex && nums[i]==nums[i-1]){continue;} 
            path.push_back(nums[i]);
            backTracking(nums,i+1);
            path.pop_back();
        }

    }
    vector<int> path;
    vector<vector<int>> ans;
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
      //path.clear();
      //ans.clear();
      sort(nums.begin(),nums.end()); //去重需要提前排序
      backTracking(nums,0);
      return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
private:
    void backTracking(vector<int>& nums,int startIndex,vector<bool>& used){
        ans.push_back(path);
        for(int i=startIndex;i<nums.size();++i){
            //去重：对同一树层使用过的元素跳过
            if(i>0 && nums[i]==nums[i-1] && used[i-1]==false){continue;} 
            path.push_back(nums[i]);
            used[i]=true;   //true 代表同一树枝使用过
            backTracking(nums,i+1,used);
            used[i]=false;
            path.pop_back();
        }
    }
    vector<int> path;
    vector<vector<int>> ans;
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
      //path.clear();
      //ans.clear();
      vector<bool> used(nums.size(),false);
      sort(nums.begin(),nums.end()); //去重需要提前排序
      backTracking(nums,0,used);
      return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
private:
    void backTracking(vector<int>& nums,int startIndex){
        ans.push_back(path);
        unordered_set<int> set;  //利用set去重
        for(int i=startIndex;i<nums.size();++i){
            if(set.find(nums[i])  !=  set.end()){continue;} //说明在 set 中找到nums[i]
            set.insert(nums[i]);

            path.push_back(nums[i]);
            backTracking(nums,i+1);
            path.pop_back();
        }

    }
    vector<int> path;
    vector<vector<int>> ans;
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
      //path.clear();
      //ans.clear();
      sort(nums.begin(),nums.end()); //去重需要提前排序
      backTracking(nums,0);
      return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
private:
    void backTracking(vector<int>& nums,vector<bool>& used){
        if(path.size()==nums.size()){
            ans.push_back(path);
            return;
        }
        for(int i=0;i<nums.size();++i){
            if(used[i]==true){continue;}   //path已经搜集过的元素，直接跳过           
            path.push_back(nums[i]);
            used[i]=true;
            backTracking(nums,used);
            used[i]=false;
            path.pop_back();        
        }
    }
    vector<int> path;
    vector<vector<int>> ans;
public:
    vector<vector<int>> permute(vector<int>& nums) {
     //path.clear();
     //ans.clear();
     vector<bool> used(nums.size(),false);
     backTracking(nums,used);
     return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
private:
    void backTracking(vector<int>& nums,vector<bool>& used){
        if(path.size()==nums.size()){
            ans.push_back(path);
            return;
        }
        for(int i=0;i<nums.size();++i){
            // used[i - 1] == true， 说明同一树枝nums[i - 1]使用过
            // used[i - 1] == false，说明同一树层nums[i - 1]使用过，直接跳过同一树层使用过的
            /*if(i>0 && nums[i]==nums[i-1] && used[i-1]==false){continue;}
            if(used[i]==false){  //注意：保证没有被使用过
                path.push_back(nums[i]);
                used[i]=true;
                backTracking(nums,used);
                used[i]=false;
                path.pop_back();          
            }*/
            if((i>0 && nums[i]==nums[i-1] && used[i-1]==false) || used[i]==true){continue;}
                path.push_back(nums[i]);
                used[i]=true;
                backTracking(nums,used);
                used[i]=false;
                path.pop_back();      
        }
    }
    vector<int> path;
    vector<vector<int>> ans;
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
     //path.clear();
     //ans.clear();
     sort(nums.begin(),nums.end());
     vector<bool> used(nums.size(),false);
     backTracking(nums,used);
     return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
private:
    void backTracking(string& s,vector<bool>& used){
        if(path.size()==s.size()){
            ans.push_back(path); return;
        }
        for(int i=0;i<s.length();++i){
            if((i>0&&s[i-1]==s[i]&&used[i-1]==false) || used[i]==true){continue;}
            path.push_back(s[i]);
            used[i]=true;
            backTracking(s,used);
            used[i]=false;
            path.pop_back();
        }
    }
    vector<string> ans;
    string path;
public:
    vector<string> permutation(string s) {
        sort(s.begin(),s.end()); //字符串可以直接排序
        vector<bool> used(s.size(),false);
        backTracking(s,used);
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {   
private:
    //判断是不是N皇后
    //1、不能同行
    //2、不能同列
    //3、不能同斜线 （45度和135度角）
    bool isValid(vector<string>& chessboard,int row,int col,int n){
        //检查列（不必检查行）
        for(int i=0;i<row;++i){
           if(chessboard[i][col]=='Q'){return false;}
        }
        //检查 45 度角是否有皇后(主斜线)
        for(int i=row-1,j=col-1; i>=0 && j>=0; i--,j--){
            if(chessboard[i][j]=='Q'){return false;}
        }
        //检查 135度角是否有皇后(副斜线)
        for(int i=row-1,j=col+1;i>=0 && j<n; i--,j++){
            if(chessboard[i][j]=='Q'){return false;}
        }
        return true;
    }

    //n是输入棋盘的大小   row用来记录棋盘到第几层
    void backTracking(vector<string>& chessboard,int n,int row){
      if(row==n){
          ans.push_back(chessboard);   //存放结果
          return;
      }
      //棋盘的宽度就是for循环的长度，递归的深度就是棋盘的高度
      for(int col=0;col<n;++col){ //每一层递归，只会选for循环（也就是同一行）里的一个元素，所以行不必检查去重
          if(isValid(chessboard,row,col,n)){
              chessboard[row][col]='Q';  //验证合法便放置皇后
              backTracking(chessboard,n,row+1);
              chessboard[row][col]='.';  //回溯，撤销皇后
          }
      }
    }
    vector<vector<string>> ans;
public:
    vector<vector<string>> solveNQueens(int n) {
      //ans.clear();
      vector<string> chessboard(n,string(n,'.'));  //重点
      backTracking(chessboard,n,0);
      return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
private:
    //判断是否为N皇后
    bool isValid(vector<string>& chessboard,int row,int col,int n){
        for(int i=0;i<row;++i){
            if(chessboard[i][col]=='Q') return false;
        }
        for(int i=row-1,j=col-1;i>=0 && j>=0;--i,--j){
            if(chessboard[i][j]=='Q') return false;
        }
        for(int i=row-1,j=col+1;i>=0 && j<n;--i,++j){
            if(chessboard[i][j]=='Q') return false;
        }
        return true;
    }
    void backTraversal(vector<string>& chessboard,int n,int row){
        if(row==n){
           count++;    //ans.push_back(chessboard); 存放结果
           return; 
        }
        for(int col=0;col<n;++col){
            if(isValid(chessboard,row,col,n)){
                chessboard[row][col]='Q';
                backTraversal(chessboard,n,row+1);
                chessboard[row][col]='.';
            }
        }
    }
    int count=0;
public:
    int totalNQueens(int n) {
        vector<string> chessboard(n,string(n,'.'));
        backTraversal(chessboard,n,0);
        return count;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
private:
    //判断棋盘是否合法
    bool isValid(vector<vector<char>>& board,int row,int col,char val){
        //1、判断行中是否重复
        for(int i=0;i<9;++i){
            if(board[row][i]==val){return false;}
        }
        //2、判断列中是否重复
        for(int j=0;j<9;++j){
            if(board[j][col]==val){return false;}
        }
        //3、判断9宫格中是否重复
        int startRow=(row/3)*3;
        int startCol=(col/3)*3;
        for(int i=startRow;i<startRow+3;++i){
            for(int j=startCol;j<startCol+3;++j){
                if(board[i][j]==val){return false;}
            }
        }
        return true;
    }
    //因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用bool返回值
    bool backTracking(vector<vector<char>>& board){
        for(int i=0;i<board.size();++i){
            for(int j=0;j<board[0].size();++j){
                if(board[i][j]!='.') continue;
                
                // 判断(i, j) 这个位置放k是否合适
                for(char k='1';k<='9';k++){
                    if(isValid(board,i,j,k)) {
                       board[i][j]=k;
                       if(backTracking(board)) return true;  // 如果找到合适一组立刻返回
                       board[i][j]='.';
                    }
                }
                return false;   // 9个数都试完了，都不行，那么就返回false.   所以没有终止条件也不会永远填不满棋盘而无限递归下去！
            }
        }
        return true;   // 遍历完没有返回false，说明找到了合适棋盘位置了
    }

public:
    void solveSudoku(vector<vector<char>>& board) {
      backTracking(board);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
//判断棋盘是否合法
bool isValid(vector<vector<int>>& board,int row,int col,char val){
//1、判断行中是否重复
for(int i=0;i<9;++i){
    if(board[row][i]==val){return false;}
}
//2、判断列中是否重复
for(int j=0;j<9;++j){
    if(board[j][col]==val){return false;}
}
//3、判断9宫格中是否重复
int startRow=(row/3)*3;
int startCol=(col/3)*3;
for(int i=startRow;i<startRow+3;++i){
    for(int j=startCol;j<startCol+3;++j){
         if(board[i][j]==val){return false;}
     }
  }
  return true;
}
//因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用bool返回值
bool backTracking(vector<vector<int>>& board){
     for(int i=0;i<board.size();++i){
         for(int j=0;j<board[0].size();++j){
            if(board[i][j]!=0) continue;
                
            // 判断(i, j) 这个位置放k是否合适
            for(int k=1;k<=9;k++){
                if(isValid(board,i,j,k)) {
                    board[i][j]=k;
                    if(backTracking(board)) return true;  // 如果找到合适一组立刻返回
                    board[i][j]=0;
                }
            }
            return false;   // 9个数都试完了，都不行，那么就返回false.   所以没有终止条件也不会永远填不满棋盘而无限递归下去！
        }
    }
    return true;   // 遍历完没有返回false，说明找到了合适棋盘位置了
}

int main(){
    vector<vector<int>> board(9,vector<int>(9));
    for(int i=0;i<9;++i){
        for(int j=0;j<9;++j){
            cin>>board[i][j];
        }
    }
    
    backTracking(board);
    
    for(int i=0;i<9;++i){
        for(int j=0;j<9;++j){
            cout<<board[i][j]<<' ';
        }
        cout<<endl;
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
private:
    void backTracking(vector<int>& nums,int startIndex){
        if(path.size()>1){
            ans.push_back(path);
        }  //注意这里不要加return ，要取树上的节点
        unordered_set<int> uset;  //去重
        for(int i=startIndex;i<nums.size();++i){
            if((!path.empty() && nums[i]<path.back()) || uset.find(nums[i])!=uset.end()) {continue;}
            uset.insert(nums[i]);  //记录本层元素是否重复使用，新的一层uset都会重新定义（清空），所以要知道uset只负责本层！

            path.push_back(nums[i]);
            backTracking(nums,i+1);
            path.pop_back();
        }
    }
    vector<int> path;
    vector<vector<int>> ans;
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
      //path.clear();
      //ans.clear();
      backTracking(nums,0);
      return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
private:
    // bool类型：因为我们只需要找到一个行程，就是在树形结构中唯一的一条通向叶子节点的路线
    bool backTracking(int ticketNum,vector<string>& ans){ //ticketNum，表示有多少个航班
        if(ans.size()==ticketNum+1){return true;}    //机场个数=航班数量+1 ，说明找到了一个行程    
        for(pair<const string,int>& target : targets[ans[ans.size()-1]]){ //pair里要有const，因为map中的key是不可修改的
            if(target.second>0){   //飞机还可以飞（航班次数的增减，判断是否飞过）
                ans.push_back(target.first);
                target.second--;
                if(backTracking(ticketNum,ans)) return true;
                target.second++;
                ans.pop_back();   
            }
        }
        return false;
    }
    // unordered_map<出发机场, map<到达机场, 航班次数>> targets
    unordered_map<string,map<string,int>> targets;
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
      //targets.clear();
      vector<string> ans;     
      for(const vector<string>& vec:tickets){targets[vec[0]][vec[1]] ++ ;}  //记录映射关系
      ans.push_back("JFK");  //起始机场

      backTracking(tickets.size(),ans);
      return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
private:    
    void backTraversal(string& s,int left,int right,int n){
        //左括号数⽬等于右括号数⽬ => 左括号数⽬ + 右括号数⽬ = 2 * n
        if(s.size()==2*n) {
            ans.push_back(s);
            return;
        }
        if(left){
            s.push_back('(');
            backTraversal(s,left-1,right,n);
            s.pop_back();
        }
        if(left<right){  //剪枝
            s.push_back(')');
            backTraversal(s,left,right-1,n);
            s.pop_back();
        }
    }
    vector<string> ans;
public:
    vector<string> generateParenthesis(int n) {
        string s;
        backTraversal(s,n,n,n);
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
private:
    bool check(vector<vector<char>>& board,vector<vector<int>>& visited,string &s,int i,int j,int k){
        if(board[i][j]!=s[k]){
            return false;
        }else if(k==s.length()-1){
            return true;
        }
        //为了防止重复遍历相同的位置，需要 visited 数组，用于标识每个位置是否被访问过。
        visited[i][j]=true;   //表示已经访问
        bool ans=false;    
        vector<pair<int,int>> directions{{0,1},{0,-1},{-1,0},{1,0}};   //重要：表示 上下左右 遍历网格
        for(const auto& dir: directions){
            int new_i=i+dir.first, new_j=j+dir.second;   //重要：表示 上下左右 遍历网格
            int row=board.size(),col=board[0].size();
            if(new_i>=0 && new_i<row && new_j>=0 &&new_j<col){
                if(!visited[new_i][new_j] && check(board,visited,s,new_i,new_j,k+1)){  //如果没有用过
                        ans=true;
                        break;
                }
            }
        }
        visited[i][j]=false;    //回溯：若此路不通，就当作没有用过
        return ans;
    }  
public:
    bool exist(vector<vector<char>>& board, string word) {
        int row=board.size(),col=board[0].size();
        vector<vector<int>> visited(row,vector<int>(col));
        for(int i=0;i<row;++i){
            for(int j=0;j<col;++j){
                if(check(board,visited,word,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
private:
    bool check(vector<vector<char>>& board,vector<vector<int>>& visited,string &s,int i,int j,int k){
        if(board[i][j]!=s[k]){
            return false;
        }else if(k==s.length()-1){
            return true;
        }
        //为了防止重复遍历相同的位置，需要 visited 数组，用于标识每个位置是否被访问过。
        visited[i][j]=true;   //表示已经访问
        bool ans=false;    
        vector<pair<int,int>> directions{{0,1},{0,-1},{-1,0},{1,0}};   //重要：表示 上下左右 遍历网格
        for(const auto& dir: directions){
            int new_i=i+dir.first, new_j=j+dir.second;   //重要：表示 上下左右 遍历网格
            int row=board.size(),col=board[0].size();
            if(new_i>=0 && new_i<row && new_j>=0 &&new_j<col){
                if(!visited[new_i][new_j] && check(board,visited,s,new_i,new_j,k+1)){  //如果没有用过
                        ans=true;
                        break;
                }
            }
        }
        visited[i][j]=false;    //回溯：若此路不通，就当作没有用过
        return ans;
    }  
public:
    bool exist(vector<vector<char>>& board, string word) {
        int row=board.size(),col=board[0].size();
        vector<vector<int>> visited(row,vector<int>(col));
        for(int i=0;i<row;++i){
            for(int j=0;j<col;++j){
                if(check(board,visited,word,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {      //大饼干留给胃口大的
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
       sort(g.begin(),g.end());
       sort(s.begin(),s.end());
       
       int ans=0;
       int index=s.size()-1;    //饼干数组的下标
       for(int i=g.size()-1; i>=0; i--){
          if(index>=0 && s[index]>=g[i]){
              ans++;
              index--;
          }
       }
       return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {      //小饼干留给胃口小的
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
       sort(g.begin(),g.end());
       sort(s.begin(),s.end());

       int ans=0;
       for(int i=0; i<s.size(); ++i){
          if(ans<g.size() && s[i]>=g[ans]){
              ans++;
          }
       }
       return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
static bool cmp(int a,int b){  //一定要加 static
    return abs(a)>abs(b);
}
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
       sort(nums.begin(),nums.end(),cmp);   //将数组按绝对值由大到小的顺序排列
       //将数组中的负数取反
       for(int i=0;i<nums.size();++i){
           if(nums[i]<0 && k>0){
               nums[i] *=-1;
               k--;
           }
       }
       //k还大于0，且为奇数，反转数组最后一个最小的数
       if(k%2==1)  nums[nums.size()-1] *=-1;

       int ans=0;
       for(int num:nums) ans+=num;
       return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five=0,ten=0;
        for(int bill: bills){
            if(bill==5){five++;}
            if(bill==10){
                if(five>0){
                    ten++;
                    five--;
                }else return false;
            }
            // 优先消耗10美元，因为5美元的找零用处更大，能多留着就多留着(此处用到贪心)
            if(bill==20){
                if(five>0 && ten>0){
                    five--;
                    ten--;
                }
                else if(five>=3){five-=3;}
                else return false;
            }
        }
        return true;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
       if(nums.size()<=1)  return nums.size();
       int curDiff=0;   //记录当前一对的差值
       int preDiff=0;   //记录前一对的差值（初始化为0）
       int ans=1;       //记录峰值个数，序列默认，最右侧有一个峰值

       for(int i=0;i<nums.size()-1;i++){
          curDiff=nums[i+1]-nums[i];
          //记录峰值 ：注意preDiff可以为0，因为初始化的为0，后面根本不会为0，考虑的是两位数的特殊情况
          if((curDiff>0 && preDiff<=0) || (curDiff<0 && preDiff>=0)){
              ans++;
              preDiff=curDiff;
          }
       }
       return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {   
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n=nums.size();
        if(n<=1)  return n;
        vector<int> up(n,1),down(n,1);
        for(int i=1;i<n;++i){
            if(nums[i]>nums[i-1]){
                up[i]=max(up[i-1],down[i-1]+1);
                down[i]=down[i-1];
            }else if(nums[i]<nums[i-1]){
                down[i]=max(down[i-1],up[i-1]+1);
                up[i]=up[i-1];
            }else{
                up[i]=up[i-1];
                down[i]=down[i-1];
            }
        }
        return max(up[n-1],down[n-1]);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {   
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n=nums.size();
        if(n<=1)  return n;
        int up=1,down=1;
        for(int i=1;i<n;++i){
            if(nums[i]>nums[i-1]){
                up=down+1;
            }else if(nums[i]<nums[i-1]){
                down=up+1;
            }
        }
        return max(up,down);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
       string strNum=to_string(n);    //转化为字符串操作更方便
       // flag用来标记赋值9从哪里开始
       int flag=strNum.size();
       for(int i=strNum.size()-1;i>0;i--){
           if(strNum[i-1]>strNum[i]){
               flag=i;
               strNum[i-1]--;  // 赋值9的前一位，需要相应的减1
           }
       }

       for(int i=flag;i<strNum.size();i++){strNum[i]='9';}
       return stoi(strNum);   //把数字字符串转换成int输出
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candyVec(ratings.size(),1); //至少有1个糖果
        for(int i=1;i<ratings.size();++i){
            if(ratings[i]>ratings[i-1]) candyVec[i]=candyVec[i-1]+1;
        }       
        for(int j=ratings.size()-1;j>0;--j){
            if(ratings[j-1]>ratings[j]) candyVec[j-1]=max(candyVec[j-1],candyVec[j]+1);
        }

        int ans=0;
        for(int i=0;i<ratings.size();++i) ans+=candyVec[i];
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    static bool cmp(const vector<int> a,const vector<int> b){
        if(a[0]==b[0])  return a[1]<b[1];  //身高相同的话则k小的站前面
        return a[0]>b[0];                  //身高降序排列
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(),people.end(),cmp);
        vector<vector<int>> ans;
        for(int i=0;i<people.size();++i){  //插入操作
            int position=people[i][1];     //people[i][1]表示第i个人前面k个比他高的人
            ans.insert(ans.begin()+position,people[i]);
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:     
    bool canJump(vector<int>& nums) {
       if(nums.size()==1) return true;   //只有一个元素，必定可以达到
       int cover=0;
       for(int i=0;i<=cover;++i){
           cover=max(i+nums[i],cover);   //i+nums[i] 表示该位置的覆盖范围
           if(cover>=nums.size()-1) return true;
       }
       return false;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int jump(vector<int>& nums) {
       int cur=0,next=0,ans=0;
       //控制移动下标i只移动到 nums.size()-2 的位置，所以移动下标只要遇到当前覆盖最远距离的下标，直接步数加一。
       for(int i=0;i<nums.size()-1;++i){
           next=max(next,nums[i]+i);
           if(i==cur){         // 移动下标等于当前覆盖的最远距离下标
               cur=next;
               ans++;
           }
       }
       return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
private:
    static bool cmp(const vector<int>& a,const vector<int>& b){return a[0]<b[0];}
public:
    int findMinArrowShots(vector<vector<int>>& points) {
       if(points.size()==0) return 0;
       sort(points.begin(),points.end(),cmp);   //按照Xstart进行由小到大的排序
       int ans=1;
       for(int i=1;i<points.size();++i){
           if(points[i-1][1] < points[i][0]) {  //不带等号：因为左闭右闭，气球将会被引爆
               ans++;
           }else{    //更新重叠气球最小右边界
               points[i][1] = min( points[i-1][1] , points[i][1] );
           } 
       }
       return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {  
private:   
    static bool cmp(const vector<int>& a,const vector<int>& b) {return a[1]<b[1];}  //按照右边界排序
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
       if(intervals.size()==0) return 0;
       sort(intervals.begin(),intervals.end(),cmp);
       int count=1;      // points不为空，至少需要一支箭
       for(int i=1;i<intervals.size();++i){
          if(intervals[i-1][1] <= intervals[i][0]){  //带等号：因为边界相互“接触”，但不表示相互重叠
              count++;
          }else{        //更新重叠区域最小右边界
              intervals[i][1]=min(intervals[i-1][1],intervals[i][1]);
          }    
       }
       return intervals.size()-count;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> partitionLabels(string s) {
      int hash[26]={0};
      for(int i=0;i<s.size();++i){         //1、统计每个字符最后出现的位置！！！
          hash[s[i]-'a']=i; 
      }  
      vector<int> ans;
      int left=0,right=0;
      for(int i=0;i<s.size();++i){         //2、从头遍历字符
          right=max(right,hash[s[i]-'a']); //找到出现的最远边界
          if(right==i){
              ans.push_back(right-left+1);
              left=i+1;
          }
      }
      return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
private:
    static bool cmp(const vector<int>& a,const vector<int>& b){return a[0]<b[0];}
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
       if(intervals.size()==0) return {};
       sort(intervals.begin(),intervals.end(),cmp);
       // 排序的参数使用了lamda表达式
       //sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});
       vector<vector<int>> ans;
       ans.push_back(intervals[0]);
       for(int i=1;i<intervals.size();++i){          
           if(intervals[i][0] <= ans.back()[1]){  //合并区间
               ans.back()[1]=max(ans.back()[1],intervals[i][1]);
           }else{
               ans.push_back(intervals[i]);
           }           
       }
       return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
      int ans=INT_MIN;
      int count=0;
      for(int i=0;i<nums.size();++i){
          count+=nums[i];
          if(count>ans) ans=count;  // 取区间累计的最大值（相当于不断确定最大子序终止位置）
          if(count<=0) count=0;     // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
      }
      return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxSubArray(vector<int>& nums) {    
        vector<int> dp(nums.size());  //此处 +1 可有可无
        dp[0]=nums[0];
        int ans=dp[0];  //此处不是定义为 INT_MIN
        for(int i=1;i<nums.size();++i){
            dp[i]=max( nums[i] , dp[i-1]+nums[i]);  //nums[i] : 从头开始计算
            if(dp[i]>ans) ans=dp[i];
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre=0,maxAns=nums[0];    //考虑了唯一值为负值
        for(const auto &num:nums){   //用num读取容器vector的值
           pre=max(pre+num,num);
           maxAns=max(pre,maxAns);
        }
        return maxAns;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        //for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历
        for(int i=0;i<cost.size();++i){
            int rest=gas[i]-cost[i];   
            int index=(i+1)%cost.size();   //从当前位置的下一个位置进行遍历
            while(rest>0 && i!=index){
                rest+=gas[index]-cost[index];
                index=(index+1)%cost.size();
            }
            if(rest>=0 && i==index) return i;
        }
        return -1;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int start=0,curSum=0,totalSum=0;
        for(int i=0;i<gas.size();++i){
            curSum +=gas[i]-cost[i];
            totalSum+=gas[i]-cost[i];
            if(curSum<0){
                start=i+1;
                curSum=0;
            }
        }
        if(totalSum<0) return -1;
        return start;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 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 {    //if 的顺序很重要 
private:
    int Traversal(TreeNode* node){
       if(node==nullptr) return 1;
       int left=Traversal(node->left),right=Traversal(node->right);
       if(left==0 || right==0){          //1、需要添加摄像头的情况：至少有一个节点没有监控
           ans++;
           return 2;
       }
       if(left==1 && right==1) return 0; //2、左右节点都有监视    
       if(left==2 || right==2) return 1; //3、左右节点至少有一个有摄像头
       return -1;    //逻辑不会走到这里，但需要有这一步
    }
    int ans=0;
public:   
    int minCameraCover(TreeNode* root) {
       if(Traversal(root)==0) {ans++;}   //4、根节点没有被监视
       return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
private:
    int Traversal(TreeNode* node){
       if(node==nullptr) return 1;
       int left=Traversal(node->left),right=Traversal(node->right);
       //使用else就不能把各个分支的情况展示出来，出错几率小
       if(left==0 || right==0){   
            ans++;
            return 2;
       }else if(left==1 && right==1){
            return 0;
       }else{
            return 1;
       }
    }
    int ans=0;
public:   
    int minCameraCover(TreeNode* root) {
       if(Traversal(root)==0) {ans++;}   //根节点没有被监视
       return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    string predictPartyVictory(string senate) {
        bool R=true,D=true;   // R = true表示本轮循环结束后，字符串里依然有R ; D同理
        //用一个变量flag记录当前参议员之前有几个敌人，进而判断自己是否被消灭了
        //flag>0 : R可以消灭D ， 反之亦然
        int flag=0;
        while(R && D){     // 一旦R或者D为false，就结束循环，说明本轮结束后只剩下R或者D了
            R=false,D=false;
            for(int i=0;i<senate.size();++i){
                if(senate[i]=='R'){
                    if(flag<0) senate[i]=0;   // 消灭R，R此时为false
                    else R=true;              // 如果没被消灭，本轮循环结束有R
                    flag++;
                }
                if(senate[i]=='D'){
                    if(flag>0) senate[i]=0;
                    else D=true;
                    flag--;
                }
            }
        }
        return R==true?"Radiant":"Dire";   // 循环结束之后，R和D只能有一个为true
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int balancedStringSplit(string s) {
        int ans=0,count=0;
        for(int i=0;i<s.size();++i){
            if(s[i]=='L') count++;
            else count--;
            if(count==0) ans++;
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        sort(intervals.begin(), intervals.end(), [](const vector<int>& u, const vector<int>& v) {
            return u[0] < v[0] || (u[0] == v[0] && u[1] > v[1]);
        });
        int ans = n;
        int rmax = intervals[0][1];
        for (int i = 1; i < n; ++i) {
            if (intervals[i][1] <= rmax) {
                --ans;
            }
            else {
                rmax = max(rmax, intervals[i][1]);
            }
        }
        return ans;
    }
};

1
2
3
4
5
6
7
class Solution {
public:
    int fib(int n) {
       if(n<2) return n;
       return fib(n-1)+fib(n-2);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int fib(int n) {
      if(n<2) return n;
      vector<int> dp(n+1);
      dp[0]=0,dp[1]=1;
      for(int i=2;i<=n;++i){
          // dp[i]=dp[i-1]+dp[i-2];
          int sum=dp[0]+dp[1];
          dp[0]=dp[1];
          dp[1]=sum;
      }
      return dp[1];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int fib(int n) {
        int MOD=1000000007;
        if(n<2) return n;
        vector<int> dp(n+1);
        dp[0]=0;dp[1]=1;
        for(int i=2;i<=n;++i){
            int sum=(dp[0]+dp[1])%MOD; //不同之处
            dp[0]=dp[1];
            dp[1]=sum;
        }
        return dp[1];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int climbStairs(int n) {
      vector<int> dp(n+1);
      dp[0]=1;dp[1]=1;
      for(int i=2;i<=n;++i){
          //利用滚动数组，降低空间复杂度
          int sum=dp[0]+dp[1];
          dp[0]=dp[1];
          dp[1]=sum;
      }
      return dp[1];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int climbStairs(int n) {
       vector<int> dp(n+1,0);
       dp[0]=1;    //完全背包记得初始化(完全背包是物品可以重复使用)
       for(int i=1;i<=n;++i){      //先遍历背包
           //进阶：2表示每次最多可以爬2个台阶
           for(int j=1;j<=2;++j){  //再遍历物品
               if(i-j>=0)  dp[i]+=dp[i-j];
           }
       }
       return dp[n];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int numWays(int n) {
        int MOD=1000000007;
        int p=0,q=1,r=1;
        for(int i=2;i<=n;++i){
            p=q;
            q=r;
            r=(p+q)%MOD;
        }
        return r;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numWays(int n) {
        int MOD=1000000007;
        if(n==0) return 1;
        vector<int> dp(n+1);
        dp[0]=1;dp[1]=1;
        for(int i=2;i<=n;++i){
            int sum=(dp[0]+dp[1])%MOD; //不同之处
            dp[0]=dp[1];
            dp[1]=sum;
        }
        return dp[1];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int translateNum(int num) {
        int a=1,b=1,c;
        int x,y=num%10;
        while(num!=0){
            num/=10;
            x=num%10;

            c=(10<=(10*x+y) && (10*x+y)<=25) ? a+b :a;
            //滑动数组优化空间
            b=a;
            a=c;

            y=x;
        }
        return a;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
       int n=cost.size();
       vector<int> dp(n+1);
       //由于可以选择下标 0 或 1 作为初始阶梯，因此有 dp[0]=dp[1]=0
       // 默认第一步都是不花费体力的，最后一步花费体力
       dp[0]=0;   
       dp[1]=0;       
       for(int i=2;i<=n;++i){
           dp[i]=min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1]) ;
       }
       return dp[n];  
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
       int n=cost.size();
       int pre=0,cur=0;
       for(int i=2;i<=n;++i){
           int next=min(pre+cost[i-2],cur+cost[i-1]) ;
           pre=cur;
           cur=next;
       }
       return cur;  
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int uniquePaths(int m, int n) {
       vector<vector<int>>  dp(m,vector<int>(n));  //定义二维数组
       for(int i=0;i<m;++i) dp[i][0]=1;
       for(int j=0;j<n;++j) dp[0][j]=1;
       for(int i=1;i<m;++i){
           for(int j=1;j<n;++j){
               dp[i][j]=dp[i-1][j]+dp[i][j-1];
           }
       }
       return dp[m-1][n-1];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        //取一个二维数组的横坐标数和纵坐标数
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        vector<vector<int>> dp(m,vector<int>(n,0));  //初始化为0
        //一旦遇到obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作
        for(int i=0;i<m && obstacleGrid[i][0]==0;++i) dp[i][0]=1;  
        for(int j=0;j<n && obstacleGrid[0][j]==0;++j) dp[0][j]=1;
        for(int i=1;i<m;++i){
            for(int j=1;j<n;++j){
                if(obstacleGrid[i][j]==1) continue;
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {    
public:
    int minPathSum(vector<vector<int>>& grid) {
        //注意二维数组 行和列的定义
        int row=grid.size(),col=grid[0].size();       
        if(row==0 && col==0) return 0;
        vector<vector<int>> dp(row+1,vector<int>(col+1));
        dp[0][0]=grid[0][0];       
        for(int j=1;j<col;++j) dp[0][j]=dp[0][j-1]+grid[0][j]; //只有一行，特别考虑             
        for(int i=1;i<row;++i) dp[i][0]=dp[i-1][0]+grid[i][0]; //只有一列，特殊考虑
        for(int i=1;i<row;++i){
            for(int j=1;j<col;++j){
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[row-1][col-1];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int row=grid.size(),col=grid[0].size();
        vector<vector<int>> dp(row+1,vector<int>(col+1));
        dp[0][0]=grid[0][0];
        for(int j=1;j<col;++j) dp[0][j]=dp[0][j-1]+grid[0][j];
        for(int i=1;i<row;++i) dp[i][0]=dp[i-1][0]+grid[i][0];
        for(int i=1;i<row;++i){
            for(int j=1;j<col;++j){
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[row-1][col-1];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int integerBreak(int n) {
       vector<int> dp(n+1);
       dp[2]=1;     //初始化 dp[0]=dp[1]=1   没有意义
       for(int i=3;i<=n;++i){
           for(int j=1;j<i;++j){
               dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));
           }
       }
       return dp[n];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int cuttingRope(int n) {
        vector<int> dp(n+1); //必须 +1
        dp[2]=1;
        for(int i=3;i<=n;++i){
            for(int j=1;j<i;++j){
                dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[n];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int cuttingRope(int n) {
        if(n<=3) return n-1;
        int a=n/3,b=n%3;  //n=3a+b
        if(b==0){
            return (int)pow(3,a);
        }else if(b==1){
            return (int)pow(3,a-1)*4;
        }else{
            return (int)pow(3,a)*2;
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int cuttingRope(int n) {
        if(n<=3) return n-1;
        int MOD=1000000007;
        int a=n/3,b=n%3;  
        long ans=1; //防止溢出 一定是long
        for(int i=1;i<a;++i){
            ans=3*ans%MOD;
        }
        if(b==0){
            return (int)(ans*3%MOD);//一定带括号
        }else if(b==1){
            return (int)(ans*4%MOD);
        }else{
            return (int)(ans*6%MOD);
        }
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int numTrees(int n) {
      vector<int> dp(n+1);
      dp[0]=1;   //空树
      for(int i=1;i<=n;++i){
          for(int j=1;j<=i;++j){
              //j-1 为以 j 为头结点左子树节点数量， i-j 为以 j 为头结点右子树节点数量
              dp[i] += dp[j-1]*dp[i-j]; 
          }
      }
      return dp[n];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n=nums.size(),sum=0;
        if(n<2) return false;
        for(auto &num:nums){sum+=num;}
        if(sum%2==1) return false;
        int target=sum/2;

        // dp[i]中的i表示背包内总和,初始化为0
        vector<int> dp(target+1,0);
        //开始0-1背包 
        //使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒叙遍历！
        for(int i=0;i<n;++i){
            for(int j=target;j>=nums[i];--j){
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        //传统的「0−1 背包问题」要求选取的物品的重量之和  不能超过  背包的总容量，
        //这道题则要求选取的数字的和  恰好等于  整个数组的元素和的一半
        if(dp[target]==target) return true;
        return false;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
       int sum=0;
       for(auto &stone:stones){sum+=stone;}
       int target=sum/2;
       vector<int> dp(target+1,0);  //初始化为0
       for(int i=0;i<stones.size();++i){    //先遍历物品
           for(int j=target;j>=stones[i];--j){   //再遍历背包，必须还是倒序遍历
               dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
           }
       }
       //分成两堆石头，一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]。
       //在计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的。
       return (sum-dp[target])-dp[target];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
private:
    void backTracking(vector<int>& candidates,int target,int startIndex,int sum){
        if(sum==target){ans.push_back(path);}
        for(int i=startIndex;i<candidates.size() && sum+candidates[i]<=target;++i){
            sum+=candidates[i];
            path.push_back(candidates[i]);
            backTracking(candidates,target,i+1,sum);
            sum-=candidates[i];   //回溯
            path.pop_back();
        }
    }
    vector<vector<int>> ans;
    vector<int> path;
public:
    int findTargetSumWays(vector<int>& nums, int target) {
       int sum=0;
       for(auto &num:nums) sum+=num;
       //没有此方案
       if(target>sum || (target+sum)%2) return 0;
       //left + right等于sum，而sum是固定的。
       //left - (sum - left) = target    =>    left = (target + sum)/2 
       //目标和问题 转化为 组合求和问题
       int bagSize=(target+sum)/2;

       sort(nums.begin(),nums.end());
       backTracking(nums,bagSize,0,0);
       return ans.size();
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
       int sum=0;
       for(auto &num:nums) sum+=num;
       if(abs(target)>sum || (target+sum)%2) return 0;
       //问题转化为 装满容量为bagSize 背包，有几种方法
       int bagSize=(target+sum)/2;
       vector<int> dp(bagSize+1,0);  //初始化为0 , dp[j] 才能正确的由dp[j - nums[i]]推导出来
       dp[0]=1;     //装满容量为0的背包，有1种方法，就是装0件物品

       for(int i=0;i<nums.size();++i){
           for(int j=bagSize;j>=nums[i];--j){
               dp[j]+=dp[j-nums[i]];
           }
       }
       return dp[bagSize];  //装满容器为bagSize背包，有  dp[bagSize]  种方法
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
         vector<vector<int>> dp(m+1,vector<int>(n+1,0));   //默认初始化为0
         for(string str:strs){   //1、遍历物品
             int zeroNum=0,oneNum=0;  
             for(char c:str){
                if(c=='0') zeroNum++;
                else oneNum++;
             }
            //2、 遍历背包容量且从后向前遍历。
            //与典型的0-1背包问题不同的是，这个物品的重量有两个维度,一个是m 一个是n，而不同长度的字符串就是不同大小的待装物品
            for(int i=m;i>=zeroNum;--i){
                for(int j=n;j>=oneNum;--j){
                  //dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。
                  //dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。
                  dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);
                }
            }
        }
        return dp[m][n];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,INT_MAX);    
        dp[0]=0;   //凑足总金额为0  所需钱币的个数一定是0
        for(int i=0;i<coins.size();++i){
            for(int j=coins[i];j<=amount;++j){
                if(dp[j-coins[i]]!=INT_MAX)   /// 如果dp[j - coins[i]]是初始值则跳过
                dp[j]=min(dp[j],dp[j-coins[i]]+1);
            }
        }
        if(dp[amount]==INT_MAX)  return -1;
        return dp[amount];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        //下标非0的dp[j]初始化为0，这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]
        vector<int> dp(amount+1,0);  
        dp[0]=1;   //凑成总金额0的货币组合数为1
        for(int i=0;i<coins.size();++i){
            for(int j=coins[i];j<=amount;++j){   //不同于0-1背包，此处不需要倒序
                //dp[j] 就是所有的 dp[j - coins[i]] 相加。
                //dp[j] 考虑coins[i]的组合总和 
                //dp[j - coins[i]]  不考虑coins[i]
                dp[j]+=dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target+1,0);
        dp[0]=1;

        //完全背包，数可以无限的用，此处求和是错误的
        //int sum=0;
        //for(auto &num:nums){sum+=num;}
        //if(sum<target) return 0;

        for(int i=1;i<=target;++i){     //可以从1开始
            for(int j=0;j<nums.size();++j){
                //防止两个数相加超过 int 的数据，故有 dp[i] < INT_MAX -dp[i-nums[j]]
                if(i-nums[j]>=0 && dp[i]<INT_MAX -dp[i-nums[j]]){
                    dp[i]+=dp[i-nums[j]];
                }
            }
        }
        return dp[target];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int numSquares(int n) {
       //dp[i]：和为i的完全平方数的最少数量为dp[i]
       vector<int> dp(n+1,INT_MAX);
       dp[0]=0;
       //先遍历物品，再遍历背包
       for(int i=1;i*i<=n;++i){
           for(int j=1;j<=n;++j){
               if(j-i*i>=0)
               dp[j]=min(dp[j],dp[j-i*i]+1);
           }
       }
       return dp[n];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numSquares(int n) {
       //dp[i]：和为i的完全平方数的最少数量为dp[i]
       vector<int> dp(n+1,INT_MAX);
       dp[0]=0;
       //先遍历背包，再遍历物品
       for(int i=1;i<=n;++i){
           for(int j=1;j*j<=i;++j){
              dp[i]=min(dp[i],dp[i-j*j]+1);
           }
       }
       return dp[n];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
         unordered_set<string> wordDictSet(wordDict.begin(),wordDict.end());
         int n=s.size();
         vector<bool> dp(n+1,false);
         dp[0]=true;
         //先遍历背包，再遍历物品。因为要求子串
         for(int i=1;i<=n;++i){
             for(int j=0;j<i;++j){
                 //如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。
                 //所以递推公式是 if( [j, i] 这个区间的子串出现在字典里 && dp[j]是true ) 那么 dp[i] = true。
                 //substr( 起始位置，截取的个数 )
                 if(wordDictSet.find(s.substr(j,i-j)) != wordDictSet.end()  &&  dp[j]==true){
                     dp[i]=true;
                 }
             }
         }
         return dp[n];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int rob(vector<int>& nums) {
       int n=nums.size();
       if(n==0) return 0;
       if(n==1) return nums[0];
       vector<int> dp(n);
       dp[0]=nums[0];
       dp[1]=max(nums[0],nums[1]);
       for(int i=2;i<n;++i){
           //如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] 
           //如果不偷第i房间，那么dp[i] = dp[i - 1]
           dp[i]=max(nums[i]+dp[i-2],dp[i-1]);
       }
       return dp[n-1];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n==0) return 0;
        if(n==1) return nums[0];
        int ans1=robRange(nums,0,n-2);  //情况1：包含首元素，不包含尾元素
        int ans2=robRange(nums,1,n-1);  //情况2：不包含首元素，包含尾元素
        //以上两种情况包含情况3：既不含首元素，又不含尾元素
        return max(ans1,ans2);
    }

    int robRange(vector<int>& nums,int start,int end){
        if(start==end) return nums[start];
        vector<int> dp(nums.size());
        dp[start]=nums[start];
        dp[start+1]=max(nums[start],nums[start+1]);
        for(int i=start+2;i<nums.size();++i){
            dp[i]=max(nums[i]+dp[i-2],dp[i-1]);
        }
        return dp[end];
    } 
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * 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:
    int rob(TreeNode* root) {
        //dp数组就是一个长度为2的数组,
        //下标为0记录 不偷该节点 所得到的的最大金钱，
        //下标为1记录  偷该节点  所得到的的最大金钱
        vector<int> ans=robTree(root);
        return max(ans[0],ans[1]);
    }
    vector<int> robTree(TreeNode* node){
        if(node==nullptr) return vector<int>{0, 0};
        //后序遍历树
        vector<int> left=robTree(node->left);
        vector<int> right=robTree(node->right);

        //偷该节点 => 左右子树不能偷
        int val1=node->val + left[0] + right[0];
        //不偷该节点 => 左右孩子就可以偷，至于到底偷不偷一定是选一个最大的
        int val2=max(left[1],left[0]) + max(right[1],right[0]);
        return {val2,val1};
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {   //贪心：最左最小值，最右最大值
public:
    int maxProfit(vector<int>& prices) {
       int ans=0;
       int low=INT_MAX;
       for(int i=0;i<prices.size();++i){
           low=min(low,prices[i]);
           ans=max(ans,prices[i]-low);
       }
       return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
     //dp[i][0] : 第i天 不持有 股票所得最多现金
     //dp[i][1] : 第i天 持有 股票所得最多现金
    int maxProfit(vector<int>& prices) {
       int len=prices.size();
       if(len==0) return 0;
       vector<vector<int>>  dp(len,vector<int>(2));
       //第0天不持有股票，不持有股票那么现金就是0   
       dp[0][0]=0;
       //第0天持有股票，此时的持有股票就一定是买入股票了
       dp[0][1]=-prices[0];

       for(int i=1;i<len;++i){
           // 第i-1天不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][0]
           // 第i天不持有股票，那么就第i天卖出，所得现金就是今天股票价格卖出所得现金即：dp[i-1][1]+prices[i]
           dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
           //第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][1]
           //第i天才持有股票，那么就是第i天买入，所得现金就是买入今天的股票后所得现金即：-prices[i]
           dp[i][1]=max(dp[i-1][1],-prices[i]);
       }
       return dp[len-1][0];   //不持有股票状态所得金钱一定比持有股票状态得到的多,故不是dp[len-1][1]
    }
};

1
2
3
4
5
6
7
8
9
10
class Solution {     //局部最优：收集每天的正利润，全局最优：求得最大利润
public:
    int maxProfit(vector<int>& prices) {
       int ans=0;
       for(int i=1;i<prices.size();++i){
           ans+=max(prices[i]-prices[i-1],0);
       }
       return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
     //dp[i][0] : 第i天 不持有 股票所得最多现金
     //dp[i][1] : 第i天 持有 股票所得最多现金
    int maxProfit(vector<int>& prices) {
       int len=prices.size();
       if(len==0) return 0;
       vector<vector<int>> dp(len,vector<int>(2));
       dp[0][0]=0;
       dp[0][1]=-prices[0];   //注意此处为负值
       for(int i=1;i<len;++i){
           //此处和“一次”买卖的唯一不同之处：dp[i-1][0]-prices[i]，
           //考虑到当第i天买入股票的时候，所持有的现金可能有之前买卖过的利润dp[i-1][0]
           dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);  
           dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);
       }
       return dp[len-1][0];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n==0) return 0;
        vector<vector<int>> dp(n,vector<int>(5,0));  //初始值为0
        dp[0][1]=-prices[0];
        dp[0][3]=-prices[0];   //注意
        for(int i=1;i<n;++i){
            dp[i][0]=dp[i-1][0];
            //第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]
            //第i天买入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);
            dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i]);
            dp[i][3]=max(dp[i-1][3],dp[i-1][2]-prices[i]);
            dp[i][4]=max(dp[i-1][4],dp[i-1][3]+prices[i]);
        }
        return dp[n-1][4];  //现金最大一定是最后一次卖出
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
       int len=prices.size();
       if(len==0) return 0;
       vector<vector<int>> dp(len,vector<int>(2*k+1,0));
       for(int j=1;j<2*k;j+=2){
           dp[0][j]-=prices[0];
       }
       for(int i=1;i<len;++i){
           for(int j=0;j<2*k-1;j+=2){
               //奇数是买入，偶数是卖出
               //注意：第i天买入股票的状态，并不是说一定是第i天买入股票
               dp[i][j+1]=max(dp[i-1][j+1],dp[i-1][j]-prices[i]);
               dp[i][j+2]=max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);
           }
       }
       return dp[len-1][2*k];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
     //0、买入
     //1、卖出：两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态
     //2、卖出：今日卖出
     //3、冷冻期
    int maxProfit(vector<int>& prices) {
       int len=prices.size();
       if(len==0) return 0;
       vector<vector<int>> dp(len,vector<int>(4,0));
       dp[0][0]-=prices[0];
       for(int i=1;i<len;++i){
           dp[i][0]=max(dp[i-1][0],max(dp[i-1][1],dp[i-1][3])-prices[i]);
           dp[i][1]=max(dp[i-1][1],dp[i-1][3]);
           dp[i][2]=dp[i-1][0]+prices[i];
           dp[i][3]=dp[i-1][2];
       }
       return max(max(dp[len-1][1],dp[len-1][2]),dp[len-1][3]); //三者最大
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
     //0、持有股票后的最多现金
     //1、不持有股票（能购买）的最多现金
     //2、不持有股票（冷冻期）的最多现金
    int maxProfit(vector<int>& prices) {
       int len=prices.size();
       if(len==0) return 0;
       vector<vector<int>> dp(len,vector<int>(3,0));
       dp[0][0]-=prices[0];
       for(int i=1;i<len;++i){
           dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);
           dp[i][1]=max(dp[i-1][1],dp[i-1][2]);
           dp[i][2]=dp[i-1][0]+prices[i];
       }
       return max(dp[len-1][1],dp[len-1][2]);  //注意到如果在最后一天（第 len-1 天）结束之后，手上仍然持有股票，那么显然是没有任何意义的,故 最多现金一定不是 do[len-1][0]
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int ans=0;
        int minPrice=prices[0]+fee;
        for(int i=1;i<prices.size();++i){
           if(prices[i]+fee<minPrice){
               minPrice=prices[i]+fee;
           }else if(prices[i]>minPrice){
               ans+=prices[i]-minPrice;
               //看成当前手上拥有一支买入价格为 prices[i]的股票，将 minPrice 更新为 prices[i]。
               //这样一来，如果下一天股票价格继续上升，我们会获得 prices[i+1]−prices[i]的收益，
               //加上这一天 prices[i]−minPrice的收益，恰好就等于在这一天不进行任何操作，而在下一天卖出股票的收益；
               minPrice=prices[i];
           }
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
     //dp[i][0] : 第i天 不持有 股票所得最多现金
     //dp[i][1] : 第i天 持有 股票所得最多现金
    int maxProfit(vector<int>& prices, int fee) {
        int len=prices.size();
        if(len==0) return 0;
        vector<vector<int>> dp(len,vector<int>(2,0));
        dp[0][1]-=prices[0];
        for(int i=1;i<len;++i){
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);//注意此处唯一的不同：多一个减去手续费的操作
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]); 
        }
        return dp[len-1][0];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len=prices.size();
        if(len==0) return 0;
        int low=INT_MAX,ans=0;
        for(int i=0;i<len;++i){
            low=min(low,prices[i]);
            ans=max(ans,prices[i]-low);
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len=prices.size();
        if(len==0) return 0;
        vector<vector<int>> dp(len+1,vector<int>(2,0));
        dp[0][1]=-prices[0];
        for(int i=1;i<len;++i){
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=max(dp[i-1][1],-prices[i]);
        }
        return dp[len-1][0];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {    //dp[i] ：i之前 包含i 的最长严格递增子序列的长度
public:
    int lengthOfLIS(vector<int>& nums) {
        int len=nums.size();
        if(len==0) return 0;
        vector<int> dp(len,1);
        int ans=1;
        for(int i=0;i<len;++i){
            for(int j=0;j<i;++j){
                //注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值
                //考虑往 dp[0…i−1] 中最长的上升子序列后面再加一个 nums[i]
                //dp[j]代表 nums[0…j] 中以 nums[j] 结尾的最长上升子序列
                //位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。
                if(nums[j]<nums[i]){  // dp[i]如果能从dp[j]这个状态转移过来，那么nums[i]必然要大于nums[j]
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
            ans=max(ans,dp[i]);
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int len=nums.size();
        if(len==0) return 0;
        int ans=1,count=1;
        for(int i=0;i<len-1;++i){
            if(nums[i+1]>nums[i]){
                count++;
            }else{count=1;}
            ans=max(ans,count);
            //if(count>ans) ans=count;
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public: 
    int findLengthOfLCIS(vector<int>& nums) {
        int len=nums.size();
        if(len==0) return 0;
        vector<int> dp(len,1);
        int ans=1;
        for(int i=0;i<len -1;++i){ //注意此处的 -1
            if(nums[i+1]>nums[i]){ //求“连续”递增的特别之处：相邻元素相比
                dp[i+1]=dp[i]+1;
            }
            ans=max(ans,dp[i+1]);
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int len=nums.size(),maxLen=0,ans=0;
        if(len<=1) return len;
        //dp[i] 用于记录最长递增子序列的长度； count[i] 用于记录最长递增子序列的个数
        vector<int> dp(len,1),count(len,1);
        for(int i=0;i<len;++i){
            for(int j=0;j<i;++j){
                if(nums[i]>nums[j]){
                    //同时考虑 dp[i] 与 count[i] 的更新
                    if(dp[j]+1>dp[i]){    //找到一个更长的递增子序列
                        dp[i]=dp[j]+1;
                        count[i]=count[j];     //重置计数:以j为结尾的子串的最长递增子序列的个数，就是最新的以i为结尾的子串的最长递增子序列的个数
                    }else if(dp[j]+1==dp[i]){  //找到两个相同长度的递增子序列
                        count[i]+=count[j]; //以i为结尾的子串的最长递增子序列的个数 就应该加上以j为结尾的子串的最长递增子序列的个数
                    }
                }
            }
            //统计结果
            if(dp[i]>maxLen){
                maxLen=dp[i];
                ans=count[i]; //重置计数
            }else if(dp[i]==maxLen){
                ans+=count[i];
            }
        }
        return ans;   
    }
};