Leetcode 113. 路径总和 II(先序遍历)

问题描述

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

Example

给定如下二叉树，以及目标和 sum = 22，

返回：

[

[5,4,11,2],

[5,8,4,5]

]

题目链接：113. 路径总和 II (难度:中等)

思路

采用先序遍历对所有路径求和，如果dang’qian

代码

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>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> path;
        vector<int> tmp;
        pathSum(root,sum,tmp,path);
        return path;
    }
    void pathSum(TreeNode* root,int sum,vector<int> &tmp,vector<vector<int>> &path){
        if(!root)
            return;
        if(!root->left && !root->right && root->val == sum){
            tmp.push_back(root->val);
            path.push_back(tmp);
            tmp.pop_back();
            return;
        }
        tmp.push_back(root->val);
        pathSum(root->left,sum - root->val,tmp,path);
        pathSum(root->right,sum - root->val,tmp,path);
        tmp.pop_back();
    }
};

执行结果： 8 ms, 20 MB

展开全文 >>

Leetcode 437. 路径总和 III(先序遍历+哈希)

问题描述

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

Example

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

返回 3。和等于 8 的路径有:

  1. 5 -> 3
  2. 5 -> 2 -> 1
  3. -3 -> 11

题目链接：437. 路径总和 III (难度：简单)

思路

从题目来看，我们需要完成两个任务，一个是路径求和，另一个则统计。对于路径求和，可以采用先序遍历来实现，而统计则可以利用哈希的方式，将路径和以及出现的次数保存下来。这里有一个注意的点：那就是从当前节点向父节点回溯时，要注意扣掉当前的路径和，以避免对父节点的另一棵子树造成影响。

代码

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:
    unordered_map<int,int> preSum;
    int getPathSum(TreeNode* root, int sum, int target){
        if(root == NULL) return 0;
        int res = 0;
        sum += root->val;
        int idx = sum - target;
        if(preSum.count(idx)){
            res += preSum[idx];
        }
        ++preSum[sum];
        res += getPathSum(root->left, sum, target);
        res += getPathSum(root->right, sum, target);
        if(--preSum[sum] <= 0)
            preSum.erase(sum);
        return res;
    }
    int pathSum(TreeNode* root, int sum) {
        preSum[0] = 1;
        return  getPathSum(root,0,sum);
    }
};

运行结果： 24 ms, 20 MB

展开全文 >>

Leetcode 1145. 二叉树着色游戏

问题描述

有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中，给出二叉树的根节点 root，树上总共有 n 个节点，且 n 为奇数，其中每个节点上的值从 1 到 n 各不相同。游戏从「一号」玩家开始（「一号」玩家为红色，「二号」玩家为蓝色），最开始时，

「一号」玩家从 [1, n] 中取一个值 x（1 <= x <= n）；

「二号」玩家也从 [1, n] 中取一个值 y（1 <= y <= n）且 y != x。

「一号」玩家给值为 x 的节点染上红色，而「二号」玩家给值为 y 的节点染上蓝色。

之后两位玩家轮流进行操作，每一回合，玩家选择一个他之前涂好颜色的节点，将所选节点一个 未着色 的邻节点（即左右子节点、或父节点）进行染色。

如果当前玩家无法找到这样的节点来染色时，他的回合就会被跳过。

若两个玩家都没有可以染色的节点时，游戏结束。着色节点最多的那位玩家获得胜利 ✌️。

现在，假设你是「二号」玩家，根据所给出的输入，假如存在一个 y 值可以确保你赢得这场游戏，则返回 true；若无法获胜，就请返回 false。

Example

输入：root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3

输出：True

解释：第二个玩家可以选择值为 2 的节点。

题目链接：1145. 二叉树着色游戏 (难度:中等)

思路

题目比较长，但思路却比较简单，我们只需要弄清楚游戏规则以及获胜的判定条件即可。对于这道题而言，比较关键的有两个点：

  • 规则：双方除了首个点以外，后续所有的着色点都必须和首个点连通。

  • 获胜判定：谁的着色点多谁就获胜

    因此我们只需要找到 x 对应的二叉树的节点，同时考虑 x 的左子树、右子树以及父结点的另一棵子树上的节点个数是否大于 n / 2。若存在这样的二叉树，则返回 true，否则返回 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
class Solution {
public:
    int count(TreeNode* root){
        if(root == nullptr)
            return 0;
        return 1 + count(root->left) + count(root->right);
    }
    TreeNode* search(TreeNode* root, int x){
        if(root == nullptr)
            return nullptr;
        if(root->val == x){
            return root;
        }
        TreeNode* l_tree = search(root->left, x);
        if(l_tree)
            return l_tree;
        TreeNode* r_tree = search(root->right, x);
        if(r_tree)
            return r_tree;
        return nullptr;
    }
    bool btreeGameWinningMove(TreeNode* root, int n, int x) {
        TreeNode* x_root = search(root, x);
        int flag = n >> 1;
        int nodes_cnt = count(x_root);
        if(n - nodes_cnt > flag)
            return true;
        int left_nodes = count(x_root->left);
        if(left_nodes > flag)
            return true;
        int right_nodes = count(x_root->right);
        if(right_nodes > flag)
            return true;
        return false;
    }
};

执行结果: 4 ms, 10.9 MB

展开全文 >>

Leetcode 95. 不同的二叉搜索树 II(根据中序序列枚举所有可能的树)

问题描述

给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。

注意：0 <= n <= 8

Example

输入：3

输出：

[

[1,null,3,2],

[3,2,null,1],

[3,1,null,null,2],

[2,1,3],

[1,null,2,null,3]

]

解释如下：

题目链接：95. 不同的二叉搜索树 II (难度：中等)

思路

由题目的要求可知，我们需要根据中序序列 [1 , … , n] 去枚举出所有可能的二叉树。对于一个已知的中序序列，所对应的可能的二叉树的个数为$\frac{C_{2n}^{n}}{n + 1}$棵(卡特兰数)。

具体策略见下：

设 f(left, right) 代表所有节点范围为 left 到 right 的所有二叉搜索树，则考虑如下情况：

1、left > right：将 nullptr 压入 ans 并返回

2、left == right：此时符合的 BST 有且仅有一棵，将其压入 ans 后返回

3、left < right：枚举 [left, right] 中的所有值 root 作为根节点，其左子树应为 l_tree = f(left, root - 1)，右子树应为 r_tree = f(root + 1, right)，分别从 l_tree 和 r_tree 中取出对应的子树，和 root 连成一棵新树，并压入 ans 中。循环结束后返回 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:
    vector<TreeNode*> helper(int left, int right){
        vector<TreeNode*> ans;
        if(left > right){
            ans.push_back(nullptr);
        }else if(left == right){
            ans.push_back(new TreeNode(left));
        }else{
            for(int i = left;i <= right;++i){
                vector<TreeNode*> l_tree = helper(left, i - 1);
                vector<TreeNode*> r_tree = helper(i + 1, right);
                for(int j = 0;j < l_tree.size();++j){
                    for(int k = 0;k < r_tree.size();++k){
                        TreeNode* root = new TreeNode(i);
                        root->left = l_tree[j];
                        root->right = r_tree[k];
                        ans.push_back(root);
                    }
                }
            }
        }
        return ans;
    }
    vector<TreeNode*> generateTrees(int n) {
        if(n == 0)
            return {};
        return helper(1, n);
    }
};

执行结果： 16ms, 13.7 MB

展开全文 >>

Leetcode 1130. 叶值的最小代价生成树(贪心算法)

问题描述

给你一个正整数数组 arr，考虑所有满足以下条件的二叉树：

每个节点都有 0 个或是 2 个子节点。

数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。（知识回顾：如果一个节点有 0 个子节点，那么该节点为叶节点。）

每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。

在所有这样的二叉树中，返回每个非叶节点的值的最小可能总和。这个和的值是一个 32 位整数。

Example

输入：arr = [6,2,4]

输出：32

解释：

有两种可能的树，第一种的非叶节点的总和为 36，第二种非叶节点的总和为 32。

Note:

  • 2 <= arr.length <= 40
  • 1 <= arr[i] <= 15
  • 答案保证是一个 32 位带符号整数，即小于 2^31。

题目链接：1130. 叶值的最小代价生成树 (难度：中等)

思路

题目要求分支节点和的最小值，由于分支节点的值 = 左右子树值的乘积， 因此要是分支和最小，应当尽量选相邻，且乘积最小的两个节点进行合并。我们可以借鉴哈夫曼树的构造方式，从 arr 中选择相邻且乘积最小的两个叶子节点 arr[i] 和 arr[j] 并合并成子树，然后将 max(arr[i], arr[j]) 作为新的叶子节点，并在逻辑上删除 min(arr[i], arr[j]) ，即在 visited 数组中将其标记为 true。重复这一过程，知道最后 arr 中只剩下最后一个元素即可。

代码

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 {
public:
    bool visited[41] = {false};
    int mctFromLeafValues(vector<int>& arr) {
        int len = arr.size();
        int ans = 0, num = len;
        while(num > 1){
            int idx = 0, tmp = INT_MAX;
            for(int i = 0;i < len - 1;++i){
                if(visited[i])
                    continue;
                int j = i + 1;
                //找到 i 后面尚未被使用到节点 j
                while(j < len && visited[j]){
                    ++j;
                }
                // 若 i 后面的所有元素都被使用过，则退出当前循环
                if(j == len)
                    break;
                if(arr[i] * arr[j] < tmp){
                    tmp = arr[i] * arr[j];
                    idx = arr[i] < arr[j] ? i : j;
                }
            }
            ans += tmp;
            visited[idx] = true;
            --num;
        }
        return ans;
    }
};

执行结果： 0 ms, 8.3 MB

展开全文 >>

Leetcode 面试题 16.18. 模式匹配(DFS + 子串分割问题)

问题描述

你有两个字符串，即pattern和value。 pattern字符串由字母”a”和”b”组成，用于描述字符串中的模式。例如，字符串”catcatgocatgo”匹配模式”aabab”（其中”cat”是”a”，”go”是”b”），该字符串也匹配像”a”、”ab”和”b”这样的模式。但需注意”a”和”b”不能同时表示相同的字符串。编写一个方法判断value字符串是否匹配pattern字符串。

Example

示例1

输入： pattern = “abba”, value = “dogdogdogdog”

输出： true

解释： “a”=”dogdog”,b=””，反之也符合规则

示例2

输入： pattern = “abba”, value = “dogcatcatdog”

输出： true

Note

  • 0 <= len(pattern) <= 1000
  • 0 <= len(value) <= 1000
  • 你可以假设pattern只包含字母”a”和”b”，value仅包含小写字母。

题目链接：面试题 16.18. 模式匹配 (难度:中等)

思路

可以将问题看成是一个带有约束条件的子串分割问题，其中约束条件为分割后的子串需要和 pattern 能够成功匹配。由于 pattern 中只包含 a 和 b，分别代表 value 的两种不同的子串。因此我们可以用回溯的方法，先尝试性地枚举 a 和 b 所可能代表的全部子串，一旦将 a 和 b 确定后，再利用 a 和 b 对 value 进行匹配。

注意：本题中空串也是子串之一

代码

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
class Solution {
public:
    // p_idx 代表当前 pattern 中字符下标
    bool dfs(int p_idx, string& pattern, string& value, vector<string>& table){
        if(pattern.size() == p_idx){
            return value.size() == 0;
        }
        int idx = pattern[p_idx] - 'a';
        // a 或 b 尚未被枚举出来
        if(table[idx] == "#"){
            for(int i = 0;i <= value.size();++i){
                string val_sub = value.substr(0, i);
                // 若 a 和 b 代表的子串相同则跳过
                if(val_sub == table[1 - idx]){
                    continue;
                }
                table[idx] = val_sub;
                string val_left = value.substr(i);
                if(dfs(p_idx + 1, pattern, val_left, table)){
                    return true;
                }
                table[idx] = "#";
            }
        }else{
            // 枚举成功后，直接利用 a 和 b 对 value 进行验证。
            int len = table[idx].size();
            string val_sub = value.substr(0, len);
            if(val_sub != table[idx]){
                return false;
            }
            string val_left = value.substr(len);
            if(dfs(p_idx + 1, pattern, val_left, table))
                return true;
        }
        return false;
    }
    bool patternMatching(string pattern, string value) {
        vector<string> table(2,"#");
        return dfs(0, pattern, value, table);
    }
};

展开全文 >>

Leetcode 1339. 分裂二叉树的最大乘积(树的前缀和 + 后序遍历)

问题描述

给你一棵二叉树，它的根为 root 。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。

由于答案可能会很大，请你将结果对 10^9 + 7 取模后再返回。

Example

输入：root = [1,2,3,4,5,6]

输出：110

解释：删除红色的边，得到 2 棵子树，和分别为 11 和 10 。它们的乘积是 110 （11*10）

题目链接：1339. 分裂二叉树的最大乘积 (难度:中等)

思路

这个问题的一个关键是如何计算删除边后的两棵子树和。这里可以采用前缀和的思想，比如假设整棵二叉树的和为 total, 则将 root 和 root->left 之间的边删除后，root 所在的子树和 = total - 以 root->left 为根节点的子树和。因此，我们可以使用先序遍历先求出 total，然后利用后序遍历枚举所有的子树和，同时记录最大积。这里要注意的是，使用 max 的时候不要进行取模操作，因为大的数取模后未必比小的数要大。因此我们用 long long 保存结果，并对最终结果进行取模。

代码：

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:
    static const int MOD = (int)1e9 + 7;
    long long ans = LLONG_MIN;
    long long Sum(TreeNode* root){
        if(root == NULL)
            return 0;
        return root->val + Sum(root->left) + Sum(root->right);
    }
    long long helper(TreeNode* root, long long total){
        if(root == NULL)
            return 0;
        long long l_sum = helper(root->left, total);
        long long r_sum = helper(root->right, total);
        long long l_product = (total - l_sum) * l_sum;
        long long r_product = (total - r_sum) * r_sum;
        ans = max(ans, max(l_product, r_product));
        return root->val + l_sum + r_sum;
    }
    int maxProduct(TreeNode* root) {
        long long total = Sum(root);
        helper(root, total);
        return ans % MOD;
    }
};

执行结果：260ms, 88.7 MB

展开全文 >>

Leetcode 865. 具有所有最深结点的最小子树(后序遍历)

问题描述

给定一个根为 root 的二叉树，每个结点的深度是它到根的最短距离。

如果一个结点在整个树的任意结点之间具有最大的深度，则该结点是最深的。

一个结点的子树是该结点加上它的所有后代的集合。

返回能满足“以该结点为根的子树中包含所有最深的结点”这一条件的具有最大深度的结点。

Example

输入：[3,5,1,6,2,0,8,null,null,7,4]

输出：[2,7,4]

解释：

我们返回值为 2 的结点，在图中用黄色标记。

在图中用蓝色标记的是树的最深的结点。
输入 “[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]” 是对给定的树的序列化表述。

输出 “[2, 7, 4]” 是对根结点的值为 2 的子树的序列化表述。

输入和输出都具有 TreeNode 类型。

题目链接：865. 具有所有最深结点的最小子树 (难度：中等)

思路

我们可以采用后序遍历，将子树的根节点和子树的叶节点深度作为键值对返回。根据这个思路，我们可以提取出递归模型：

设 f(root, depth) = {tree, depth} 代表 root 深度为 depth 的叶节点子树 tree，则考虑：

  1. 递归边界：当 root 为叶结点时，应当返回 {root, depth}
  2. 递归体(l_tree 代表 root 的左最深子树，r_tree 代表 root 的右最深子树。)
  • 若 l_tree 的深度和 r_tree 的深度同，合并两棵子树
  • 若 l_tree 和 r_tree 的深度不同，返回其中更深的子树

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    typedef pair<TreeNode*, int> pair;
    pair helper(TreeNode* root, int depth){
        if(root == NULL)
            return {NULL, 0};
        pair l_tree = helper(root->left, depth + 1);
        pair r_tree = helper(root->right, depth + 1);
        if(root->left == NULL && root->right == NULL){
            return {root, depth};
        }
        if(l_tree.second == r_tree.second){
            return {root, l_tree.second};
        }
        return l_tree.second < r_tree.second ? r_tree : l_tree;
    }
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        return helper(root, 0).first;
    }
};

执行结果： 8 ms, 14.5 MB

展开全文 >>

Leetcode 面试题 04.08. 首个共同祖先

问题描述

设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。注意：这不一定是二叉搜索树。

注：一个节点的公共祖先可以是它本身

Example

示例1

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

输出: 3

解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例2

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

输出: 5

解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

题目链接：面试题 04.08. 首个共同祖先 (难度：中等)

思路

对于这个问题，我们可以将其分为两种情况：

  • p 和 q 之间不存在祖先关系，这是公共祖先的基本情况
  • p 和 q 之间存在祖先关系，则 p 或 q 为公共祖先

根据这两种情况，我们提取递归模型：

设 f(root, p, q) 代表 root 中 p 和 q 的首个公共祖先，则有

  1. 当 f(root->left, p, q) && f(root->right, p, q) 成立，显然此时 root 为公共祖先
  2. 当 f(root->left, p, q) || f(root->right, p, q) 成立，则 p 为 q 的祖先或 q 为 p 的祖先，返回首个访问到的节点。
  3. 当 f(root->left, p, q) 和 f(root->right, p, q) 均为 NULL，说明 p 和 q 均不在 root 中，返回 NULL

代码

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

执行结果： 20 ms，14.4 MB

展开全文 >>

Leetcode 958. 二叉树的完全性检验（层次遍历）

问题描述

给定一个二叉树，确定它是否是一个完全二叉树。

百度百科中对完全二叉树的定义如下：

若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2h 个节点。）

Example

示例1：

输入：[1,2,3,4,5,6]

输出：true

解释：最后一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），且最后一层中的所有结点（{4,5,6}）都尽可能地向左。

示例2：

输入：[1,2,3,4,5,null,7]

输出：false

解释：值为 7 的结点没有尽可能靠向左侧。

题目链接：958. 二叉树的完全性检验 (难度:中等)

思路

对完全二叉树进行层次遍历即可发现，在层次序列当中，所有的非空节点都是连在一起的，而所有的空节点也是连在一起，并靠在非空节点的后方。因此我们只需要对树进行层次遍历，一旦队头出现空节点则检查剩下的队列当中的节点是否含有非空节点，若有则必定不是完全二叉树，若没有则为完全二叉树

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        queue<TreeNode*> my_queue;
        my_queue.push(root);
        TreeNode* cur = NULL;
        while((cur = my_queue.front()) != NULL){
            my_queue.push(cur->left);
            my_queue.push(cur->right);
            my_queue.pop();
        }
        while(!my_queue.empty()){
            if(my_queue.front() != NULL)
                return false;
            my_queue.pop();
        }
        return true;
    }
};

执行结果： 0 ms, 10.5 MB

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

主要涉及技术：
C++, 后端开发, lua语言
开源爱好者、Linux

热爱阅读，健身，旅游及美食

联系QQ:519788069