LeetCode-202009

77. Combinations-20200908

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
Example 2:

Input: n = 1, k = 1
Output: [[1]]

Constraints:

1 <= n <= 20
1 <= k <= n

首先想着用循环做… 刚开始刷题都没什么思想，想了想行不通，实际上这道题应该用回溯来做，第一个算法是看题解做的（TwT脑子还没转过来），第二个用的是离散树章的前缀码，数据结构中也有讲到，选择或者不选择，就可以组合出不重复的前缀码。

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ret;
        if (n <= 0) {
            return ret;
        }
        vector<int> cur;
        // DFSSolve(ret, cur, n, k, 1);
        DFSanother(ret, cur, 1, 0, n, k);

        return ret;
    }

    void DFSSolve(vector<vector<int>> &ret, vector<int>cur, int n, int k, int level) {
        if (cur.size() == k) {
            ret.push_back(cur);
            return;
        }
        if (cur.size() > k) {
            return;
        }

        for (int i = level; i <= n; i++) {
            cur.push_back(i);
            DFSSolve(ret, cur, n, k, i+1);
            cur.pop_back();
        }
    }

    void DFSanother(vector<vector<int>> &ret, vector<int>&cur, int step, int selected, int n, int k) {
        if (selected == k) {
            ret.push_back(cur);
            return;
        }
        if (step == n + 1) {
            return;
        }
        
        DFSanother(ret, cur, step+1, selected, n, k); 	// not select
        cur.push_back(step); // select
        DFSanother(ret, cur, step+1, selected+1, n, k);
        cur.pop_back();
    }
};

第二个解法本来是有样例[20, 16]没有通过(tle)，后来问了问dl发现是cur没有被引用，导致复制的时间边长了，加上引用就过了。

33. Combination sum-20200909

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

Constraints:

1 <= candidates.length <= 30
1 <= candidates[i] <= 200
Each element of candidate is unique.
1 <= target <= 500

这道题跟昨天的类似，一样用回溯，一开始写好了程序发现样例有[2,2,3]的重复，原因在第二层递归的时候重新把前面的元素加进去，导致了重复，只要添加一个begin变量，每次递归的时候从当前的idx开始循环（不是下一个，因为元素可以重复），添加后成功通过。

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ret;
        vector<int> cur;
        int sum = 0;
        
        D(ret, cur, candidates, candidates.size(), target, 0, sum);
        return ret;

    }

    void D(vector<vector<int>> &ret, vector<int> &cur, vector<int> &candidates, int size, int target, int step, int &sum) {
        if (sum == target) {
            ret.push_back(cur);
            
            return;
        } 
        if (sum > target) {
            return;
        }


        for (int i = step; i < size; i++) {
            cur.push_back(candidates[i]);
            sum+=candidates[i];
            D(ret, cur, candidates, size, target, i, sum);
            sum -= cur.back(); // backtracking
            cur.pop_back();
        }
    } 
};

也有逐个减去target的写法，就是sum和0的区别。

40. Combination Sum II - 20200910

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Example 2:

Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]

这道题与昨天的区别在于candidates中会出现重复的数字而不能对某一index的元素重复选择，一开始我考虑用一个pend的布尔数组来做，但是写不出来，看了看题解，发现和昨天的区别不大，只是先对candidates进行排序，然后加上一个判定条件即可。

class Solution {
public:

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> ret;
        vector<int> cur;
        int sum = 0;
        sort(candidates.begin(), candidates.end());// 先进行排序
        
        D(ret, cur, candidates, candidates.size(), target, 0, sum);
        return ret;

    }

    void D(vector<vector<int>> &ret, vector<int> &cur, vector<int> &candidates, int size, int target, int step, int &sum) {
        if (sum == target) {
            ret.push_back(cur);
            return;
        } 
        if (sum > target) {
            return;
        }
        
        for (int i = step; i < size; i++) {
            if (i>step && candidates[i-1] == candidates[i]) continue; // 相同的分支(在前一个元素的下一层），避免重复
            cur.push_back(candidates[i]);
            sum+=candidates[i];
            D(ret, cur, candidates, size, target, i+1, sum);
            sum -= cur.back();
            cur.pop_back();
        }
    } 
};

此外也可以通过hashmap来进行操作，先排序，然后建立一个candidates元素的数量map，像搭积木一样，从不加到加到能加的最大值。

class Solution
{
public:
    vector<pair<int, int>> freq;
    vector<vector<int>> ans;
    vector<int> tmpqueue;

    vector<vector<int>> combinationSum2(vector<int> &candidates, int target)
    {
        sort(candidates.begin(), candidates.end());
        for (int i : candidates)
        {
            if (freq.empty() || i != freq.back().first)
            {
                freq.emplace_back(i, 1);
            }
            else
            {
                freq.back().second++;
            }
        }
        dfs(0, target);
        return ans;
    }

    void dfs(int pos, int rest)
    {
        if (rest == 0)
        {
            ans.push_back(tmpqueue);
            return;
        }
        if (pos == freq.size() || rest < freq[pos].first) 
            return;

        dfs(pos + 1, rest); // pos处的数字没有被选择

        int cnt = min(rest / freq[pos].first, freq[pos].second);
        for (int i = 1; i <= cnt; i++)
        {
            tmpqueue.push_back(freq[pos].first);
            dfs(pos + 1, rest - i * freq[pos].first);
        }
        for (int i = 0; i < cnt; i++)
            tmpqueue.pop_back();
    }
};

216. Combination Sum III - 20200911

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Note:

All numbers will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Example 2:

Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]

这道题还挺简单的，直接上代码应该能够直接看懂

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> cur;

    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k, n, 1, 0);
        return ret;    
    }

    void dfs(int size, int rest, int step, int cnt) {
        if (cnt == size && rest == 0) {
            ret.push_back(cur);
            return;
        }
      	// two condition can't be switched, if rest == 0, it meets the 'rest < step' condition.
        if (cnt > size || rest < step) {
            return;
        }
        for (int i = step; i <= 9; i++) {
            cur.push_back(i);
            rest -= i;
            dfs(size, rest, i+1, cnt+1);
            cur.pop_back(); // backtrack
            rest += i;
        }
    }
};

然后看题解。。。果然if判断还是比较耗时，减少一层，上方的12-19行代码换为

if (cnt >= size) {
  if (cnt == size && rest == 0) 
    ret.push_back(cur);
  return;
}
if(rest < step) {
  return;
}

0ms也太帅辣！

637. Average of Levels in Binary Tree - 20200912

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
Example 1:

Input:

3

/ \

9 20

/ \

15 7

Output: [3, 14.5, 11]

Explanation:
The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].
Note:
The range of node’s value is in the range of 32-bit signed integer.

解法一：非递归BFS

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<double> ret;
    queue<TreeNode*> nodeQueue;
    double tmp;

    vector<double> averageOfLevels(TreeNode* root) {
        bfs(root);
        return ret;
    }

    void bfs(TreeNode* root) {
        int curCnt = 0, nextCnt = 0;
        nodeQueue.push(root);
        TreeNode* node;
        curCnt = 1;
        int cnt = 1;
        while(!nodeQueue.empty()) {
            node = nodeQueue.front();
            nodeQueue.pop();
            tmp+=node->val;
            curCnt -= 1;
            if (node->left){ nodeQueue.push(node->left);nextCnt+=1; }
            if (node->right) {nodeQueue.push(node->right);nextCnt+=1; }
            if (curCnt == 0) {
                ret.push_back(tmp / cnt);
                tmp=0;
                cnt = curCnt = nextCnt;
                nextCnt=0;
            }
        }
    }
};

解法二：DFS

这个思路比较简单，就是遍历到所有的结点然后计算

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<double> ret;
    vector<int> cntArr;
    vector<pair<int, int>> nodes;
    int cnt;

    vector<double> averageOfLevels(TreeNode* root) {
        dfs(root, 0);
        ret = vector<double>(cnt+1, 0);
        cntArr = vector<int>(cnt+1, 0);
        for (int i = 0; i < nodes.size(); i++) {
            ret[nodes[i].second] += nodes[i].first;
            cntArr[nodes[i].second]++;
        }
        for (int i = 0; i <= cnt; i++) {
            ret[i] /= cntArr[i];
        }
        return ret;
    }

    void dfs(TreeNode* root, int level) {
        nodes.push_back({root->val, level});
        if (cnt < level) { cnt = level; }
        if (root->left) { dfs(root->left, level+1); }
        if (root->right) { dfs(root->right, level+1); }
        return;
    }
}

79. Word Search - 20200913

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

board =
[
[‘A’,‘B’,‘C’,‘E’],
[‘S’,‘F’,‘C’,‘S’],
[‘A’,‘D’,‘E’,‘E’]
]

Given word = “ABCCED”, return true.
Given word = “SEE”, return true.
Given word = “ABCB”, return false.

Constraints:

board and word consists only of lowercase and uppercase English letters.

1 <= board.length <= 200

1 <= board[i].length <= 200

1 <= word.length <= 10^3

过程中可以使用一个tmp来代替pend数组，然后就可以通过tmp回溯。

class Solution {
public:
    int m, n;
    int wordLen;
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size();
        n = board[0].size();
        wordLen = word.length();
        for (int i = 0;i<m;i++)
            pend.push_back(vector<int>(n, 0));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                if (recur(board, i, j, word, 0)) return true;
            }
        return false;
    }

    bool recur(vector<vector<char>> &board, int i, int j, string &word, int idx) {
        if (i < 0 || i >= m || j < 0 || j >= n || word[idx] != board[i][j])
            return false;

        if (idx == wordLen-1)
            return true;
        
        char tmp = board[i][j]; // save tmp for backtracking
        board[i][j]='!';
        if (
            (recur(board, i - 1, j, word, idx+1) ||
            recur(board, i + 1, j, word, idx+1) ||
            recur(board, i, j - 1, word, idx+1) ||
            recur(board, i, j + 1, word, idx+1))
        ) 
        return true;
        else {
            board[i][j]=tmp;
            return false;
        }
    }

};

94. Binary Tree Inorder Traversal - 20200914

Given a binary tree, return the inorder traversal of its nodes’ values.

Example:

Input: [1,null,2,3]

1

\

2

/

3

Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

算是复习吧，非递归的不记得了还去翻代码了。。数据结构白给。

但有什么比下雨天喝咖啡刷题更棒的呢。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> ret;

    vector<int> inorderTraversal(TreeNode* root) {
        traversal(root);
        return ret;
    }
    
    // void recur(TreeNode* root) {

    //     if (!root)
    //         return;
    //     else {
    //         if (root->left) recur(root->left);
    //         ret.push_back(root->val);
    //         if (root->right) recur(root->right);
    //     }
    //     return;
    // }

    void traversal(TreeNode* root) {
        if (!root) return;
        TreeNode* node = root;
        vector<TreeNode*> nodes;

        while (!nodes.empty() || node) {
            while (node) {
                nodes.push_back(node);
                node=node->left;
            }
            if (!nodes.empty()) {
                node = nodes.back();
                nodes.pop_back();
                ret.push_back(node->val);
                node=node->right;
            }
        }
    }
};

由于是学过的内容所以再来一道

377. Combination Sum IV - 20200914

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?

Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.

有一个dp的解法，但是c++由于超范围了用不了

int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target+1, 0);
        dp[0] = 1;
        for (int i = 0; i <= target; i++)
            for (int x: nums)
                if (x <= i) {

                    dp[i] += dp[i-x];
                    // cout << "dp[" << i <<"] += dp[" << i-x << "] -- dp[" << i << "] is " << dp[i]  << endl;
                }
        return dp[target];
    }

然后看提交记录里的，竟然也有用这个算法解的

class Solution {
public:

    int combinationSum4(vector<int>& nums, int target) {
        int len = nums.size();
        vector<long long> dp(target+1, 0);
        for(int i=1; i<=target; i++){
            for(int j=0; j<len; j++){
                if(i-nums[j]==0){
                    dp[i] += 1;
                }
                else if(i-nums[j]>0 && dp[i-nums[j]]!=0){
                    dp[i] += dp[i-nums[j]];
                }
            }
            dp[i] = dp[i]%10000000000;
        }
        return dp[target];
    }
};

简化一下

class Solution {
public:

    int combinationSum4(vector<int>& nums, int target) {
      	
        int len = nums.size();
      	// 加入边界判断
      	if (len == 0 || target == 0) return 0;
        vector<long long> dp(target+1, 0);
        dp[0] = 1;
        for(int i=1; i<=target; i++){
            for(int j=0; j<len; j++){
                if (i-nums[j] >= 0) {
                    dp[i] += dp[i-nums[j]];
                }
            }
            dp[i] = dp[i]%10000000000;
        }
        return dp[target];
    }
};

还可以用键值对来存储，这个采用递归，也采用了记忆化的方法。

class Solution {
public:
    int ret;
    int size;
    unordered_map<int, int> dp;

    int combinationSum4(vector<int>& nums, int target) {
        this->ret = 0;
        this->size = nums.size();
        return count(nums, target);
    }

    int count(const vector<int> &nums, int target) {
        if (target == 0) return 1;
        if (dp.count(target) != 0) return dp[target];
        int res = 0;
        for (int i=0; i<size;i++)
            if (target-nums[i]>=0)
                res+=count(nums, target-nums[i]);
        dp[target] = res;
        return dp[target];
    }
};

37. Sudoku Solver - 20200915

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Empty cells are indicated by the character ‘.’.

A sudoku puzzle…

…and its solution numbers marked in red.

Note:

The given board contain only digits 1-9 and the character ‘.’.

You may assume that the given Sudoku puzzle will have a single unique solution.

The given board size is always 9x9.

今天是困难题。。。最简单的方法是递归+回溯，主要思考难点在如何实现递归，官方解法在于声明三个bool数组，通过判断bool数组里的数字是否被填充，来判断第i行，第j列和第3*3的block里这个数字是否被选择，那么首先定义三个bool数组。

1
2
3

bool line[9][9];
bool column[9][9];
bool block[3][3][9];

然后定义一个vector<pair<int, int>>，在main里先进行遍历数独，如果为空，放进vector，如果不为空，那就在三个bool数组里设置

class Solution
{
public:
    bool line[9][9];
    bool column[9][9];
    bool block[3][3][9];
    bool valid;
    vector<pair<int, int>> spaces;

    void solveSudoku(vector<vector<char>> &board)
    {
        memset(line, false, sizeof(line));
        memset(column, false, sizeof(column));
        memset(block, false, sizeof(block));

        valid = false;

        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if (board[i][j] == '.')
                {
                    spaces.emplace_back(i, j);
                }
                else
                {
                    int digit = board[i][j] - '0' - 1;
                    line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
                }
            }
        }

        dfs(board, 0);
    }

    void dfs(vector<vector<char>> &board, int pos)
    {
        if (pos == spaces.size())
        {
            valid = true;
            return;
        }
        auto [i, j] = spaces[pos];
        for (int digit = 0; digit < 9 && !valid; digit++)
        {
            if (!line[i][digit] && !column[j][digit] && !block[i / 3][j / 3][digit])
            {
                line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
                board[i][j] = digit + '0' + 1;
                dfs(board, pos + 1);
                line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = false;
            }
        }
    }
};

同时，通过位运算代替布尔数组也是不错的选择

class Solution
{
private:
    int line[9];
    int column[9];
    int block[3][3];
    bool valid;
    vector<pair<int, int>> spaces;

public:
    void flip(int i, int j, int digit)
    {
        line[i] ^= (1 << digit);
        column[j] ^= (1 << digit);
        block[i / 3][j / 3] ^= (1 << digit);
    }

    void dfs(vector<vector<char>> &board, int pos)
    {
        if (pos == spaces.size())
        {
            valid = true;
            return;
        }

        auto [i, j] = spaces[pos];
        int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
        for (; mask && !valid; mask &= (mask - 1))
        {
            int digitMask = mask & (-mask);
            int digit = __builtin_ctz(digitMask);
            flip(i, j, digit);
            board[i][j] = digit + '0' + 1;
            dfs(board, pos + 1);
            flip(i, j, digit);
        }
    }

    void solveSudoku(vector<vector<char>> &board)
    {
        memset(line, 0, sizeof(line));
        memset(column, 0, sizeof(column));
        memset(block, 0, sizeof(block));
        valid = false;

        for (int i = 0; i < 9; ++i)
        {
            for (int j = 0; j < 9; ++j)
            {
                if (board[i][j] == '.')
                {
                    spaces.emplace_back(i, j);
                }
                else
                {
                    int digit = board[i][j] - '0' - 1;
                    flip(i, j, digit);
                }
            }
        }

        dfs(board, 0);
    }
};

同学了解一些bitset~

bitset可以理解为二进制数组，同时节省空间，可以正常进行位运算，也可以随意进行转换。可以把上面的int换为bitset<9>

226. Invert Binary Tree - 20200916

Invert a binary tree.

/**
 * 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* tmp;
    TreeNode* invertTree(TreeNode* root) {
        dfs(root);
        return root;
    }

    void dfs(TreeNode* root) {
        if (!root) return;
        swap(root->left, root->right);
        
        if (root->left)
            dfs(root->left);
        if (root->right)
            dfs(root->right);
        return;
    }
};

78. Subsets - 20200920

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

用前缀码的思想可以做这道题，但是效率稍微有一点点低

class Solution {
public:
    vector<int> cur;
    vector<vector<int>> ret;

    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return ret;

    }

    void dfs(const vector<int>& nums, int step) {
        if (step == nums.size()) {
            ret.push_back(cur);
            return;
        }

        cur.push_back(nums[step]);
        dfs(nums, step+1);
        cur.pop_back();
        dfs(nums, step+1);
        return;
    }
};

538. Convert BST to Greater Tree - 20200921

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Example:

Input: The root of a Binary Search Tree like this:

5

/ \

2 13

Output: The root of a Greater Tree like this:

18

/

20 13

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> nodes;


    TreeNode* convertBST(TreeNode* root) {
        dfs(root);
        add(root);
        return root;
    }

    void dfs(TreeNode* node) {
        if(!node) return;
        nodes.push_back(node->val);
        if (node->left) dfs(node->left);
        if (node->right) dfs(node->right);
    }

    void add(TreeNode* node) {
        if(!node) return;
        int ori = node->val;
        for (int i = 0; i < nodes.size(); i++)
            if (nodes[i] > ori) node->val+=nodes[i];
        if (node->left) add(node->left);
        if (node->right) add(node->right);
    }
};

968. Binary Tree Cameras - 20200922

Given a binary tree, we install cameras on the nodes of the tree.

Each camera at a node can monitor its parent, itself, and its immediate children.

Calculate the minimum number of cameras needed to monitor all nodes of the tree.

Example 1:

Input: [0,0,null,0,0]

Output: 1

Explanation: One camera is enough to monitor all nodes if placed as shown.

Example 2:

Input: [0,0,null,0,null,0,null,null,0]

Output: 2

Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

Note:

The number of nodes in the given tree will be in the range [1, 1000].
Every node has value 0.

自下往上思考，类似某个最基础的dp，从root有无相机出发，自己有，那么上一个结点被覆盖，不需要相机，如果自己没有，则考虑子树有无，然后采用二叉树的后序遍历，达到自下而上的效果，先左右再进行操作，需要思考如果root为空和判断left和right的顺序，PNEED应该是最优先的，其次是HAS，再是NONEED，但是这个解法效率比较低

/**
 * 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:
    const int HAS = 0; // 子树没有相机 自己有
    const int PNEED = 1; // 子树没有相机 自己没有 父母要有
    const int NONEED = 2; // 子树有相机 自己没有


    int ret; // 答案全局变量

    int minCameraCover(TreeNode* root) {
        ret = 0;
        if (dfs(root) == PNEED) ret++;
        return ret;
    }

    int dfs(TreeNode* root) {
        if (!root) return NONEED; // 那么最底下的树被其父母覆盖就行
        
        int left = dfs(root->left);
        int right = dfs(root->right);

        if (left == PNEED || right == PNEED) {
            ret++;
            return HAS;
        }
        if (left == HAS || right == HAS) return NONEED;
        if (left == NONEED || right == NONEED) return PNEED;
        
        return NONEED;
    }
};

617. Merge Two Binary Trees - 20200923

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

挺简单的一道题，可以直接在第一棵树上做操作

t1为空
- t2不空，t1=t2，返回
- t2空，返回
t1值+=t2值
子树为空
- t2子树不空，直接指到t2，返回
- t2子树空，返回
子树不空
- 进行下一次dfs

/**
 * 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* mergeTrees(TreeNode* t1, TreeNode* t2) {
        dfs(t1, t2);
        if (!t1)
            if (t2)
                t1=t2;
        return t1;
    }

    void dfs(TreeNode* t1, TreeNode* t2) {
        if (!t1 || !t2) return;
        if(t2) t1->val+=t2->val;
        else return;

        if(!t1->left) {
            if (t2->left) {
                t1->left = t2->left;
            }
        } else {
            dfs(t1->left, t2->left);
        }
      
        if (!t1->right) {
            if (t2->right) {
                t1->right = t2->right;
            }
        } else {
            dfs(t1->right, t2->right);
        }
        
    }
};

501. Find Mode in Binary Search Tree - 20200924

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
Both the left and right subtrees must also be binary search trees.

For example:
Given BST [1,null,2,2],

1

\

2

/

2

return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

利用一个Cur，CurCount，MaxCount来作为全局变量，遍历的时候采取中序遍历，首先判断Cur是否跟当前结点的相同，如果相同那么CurCnt++就可以，不然就把Cur变为当前的，并且把curCnt置为1，再进行CurCnt和MaxCnt进行对比，如果CurCnt更大，那么ret清空，之后就思路简单了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> ret;
    int cur;
    int curCnt;
    int maxCnt;

    vector<int> findMode(TreeNode* root) {
        cur = -1;
        maxCnt = 0;
        curCnt = 1;
        dfs(root);
        return ret;
    }

    void dfs(TreeNode* root) {
        if (!root) return;

        dfs(root->left);

        if (cur == root->val) curCnt++;
        else {
            cur = root->val;
            
            // cur = root->val;
            curCnt = 1;
        }
        if (curCnt >= maxCnt) {
            if (curCnt > maxCnt) {
                ret.clear();
                maxCnt = curCnt;
            }
            // cur = root->val;
            ret.push_back(cur);
        }

        dfs(root->right);
    }
};

106. 从中序与后序遍历序列构造二叉树 - 20200925

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
  3
/ \

9 20

/ \

15 7

好难，只能看题解做了

/**
 * 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:
    int post_idx;
    unordered_map<int, int> idx_map;

    TreeNode* helper(int in_left, int in_right, vector<int>& inorder, vector<int>& postorder) {
        if (in_left > in_right) {
            return nullptr;
        }

        int root_val = postorder[post_idx];
        TreeNode* root = new TreeNode(root_val);

        int index = idx_map[root_val];
        post_idx--;
        root->right = helper(index+1, in_right, inorder, postorder);
        root->left = helper(in_left, index-1, inorder, postorder);
        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        post_idx = postorder.size() - 1;

        int idx = 0;
        for (auto& val : inorder) {
            idx_map[val] = idx++;
        }
        return helper(0, inorder.size() - 1, inorder, postorder);
    }
};

113. 路径总和 II - 20200926

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

简单的递归和回溯，记住好pop的时机即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> ret;
    vector<int> cur;

    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        dfs(root, sum);
        return ret;
    }

    void dfs(TreeNode* root, int rest) {
        if (!root) return;

        cur.push_back(root->val);
        // rest -= root->val;
        if (!root->left && !root->right) {
            if (rest - root->val == 0) {
                ret.push_back(cur); 
            }
            cur.pop_back();
            return;
        }
        dfs(root->left, rest - root->val);
        dfs(root->right, rest - root->val);
        cur.pop_back();
    }
};

235. 二叉搜索树的最近公共祖先 - 20200927

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

题目太长点开看详情吧，这道题要求求公共祖先，那么dfs深度遍历二叉树是一个不错的想法，但是要带着两个参数一起寻找，如果是最基础的想法可以是写一个搜索二叉树的查找结点算法，然后两个数分别查找同时记录路径，再从两条路径里开始找，想了想实在是麻烦，于是使用深度遍历。

先判断找到的条件，如果p和q任意一个等于当前结点的值，那么根据例2和搜索二叉树的性质，那么当前结点必定是最近的公共祖先，同时，如果两个值分别在当前结点的两边，即一个大于一个小于，那么当前结点也是最近的公共祖先。

找不到的情况需要判断p是小于还是大于当前结点的值（因为p和q都是在结点的一边了），如果大于，则返回右子树的搜索结果，反之则返回左子树的搜索结果。

/**
 * 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:
    int cp, cq;


    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        cp = p->val;
        cq = q->val;
        if (cp > cq) swap(cp, cq);
        TreeNode* ret = dfs(root);
        return ret;
    }

    TreeNode* dfs(TreeNode* root) {
        int cur = root->val;
        if ((cp == cur || cq == cur) || (cp < cur && cur < cq))
            return root;
        else if (cp < cur) {
            return dfs(root->left);
        } else {
            return dfs(root->right);
        }
    }
};

117. 填充每个节点的下一个右侧节点指针 II - 20200928

给定一个二叉树

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

进阶：

你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。


class Solution {
public:
    queue<Node*> nodeQueue;

    Node* connect(Node* root) {
        levelTraversal(root);
        return root;
    }

    void levelTraversal(Node* root) {
        if (!root) return;
        int curCnt = 0, nextCnt = 0;
        nodeQueue.push(root);
        Node* node;
        curCnt = 1;
        while(!nodeQueue.empty()) {
            node = nodeQueue.front();
            nodeQueue.pop();
            curCnt--;
            node->next = curCnt > 0 ? nodeQueue.front() : nullptr;
            if (node->left){ nodeQueue.push(node->left);nextCnt++; }
            if (node->right) {nodeQueue.push(node->right);nextCnt++; }
            if (curCnt == 0) {
                curCnt = nextCnt;
                nextCnt = 0;
            }
        }
    }
};

145. 二叉树的后序遍历 - 20200929

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

没什么时间，直接用递归做了。如果要用迭代的话，直接做相对比较麻烦，可以曲线救国，因为后序遍历的倒序是先序遍历左右子树的访问顺序交换，即先根节点，再右子树、左子树，然后再把结果倒序输出即为后续遍历。

/**
 * 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> ret;

    vector<int> postorderTraversal(TreeNode* root) {
        dfs(root);
        return ret;
    }

    void dfs(TreeNode* root) {
        if (!root) return;

        dfs(root->left);
        dfs(root->right);
        ret.push_back(root->val);
    }
};

701. 二叉搜索树中的插入操作 - 20200930

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。

水题还忘记打卡了。。。

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (!root) {
            root = new TreeNode(val);
        } else {
            TreeNode* node = root;
            bool pend;
            while(true) {
…            if (pend)
                node->right = new TreeNode(val);
            else node->left = new TreeNode(val);
        }
        return root;
    }
};