标签： medium

目标

树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，任何一个没有简单环路的连通图都是一棵树。

给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。

可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。

请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。

树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。

说明：

• 1 <= n <= 2 * 10^4
• edges.length == n - 1
• 0 <= ai, bi < n
• ai != bi
• 所有 (ai, bi) 互不相同
• 给定的输入 保证 是一棵树，并且 不会有重复的边

思路

一看到这个题目就想起了换根动态规划，参考2581_统计可能的树根数目。

这个题是medium，但是感觉比上面参考那个hard题难多了，状态转换方程很难想。基本都是靠错误案例调试出来的。最开始写的dp方法调试了好几个小时，测试通过但是超时。然后开始怀疑dp根本就没法解，因为换根后状态是变化的，需要动态调整高度，并且还要区分当前节点是否为原来的根提供了最大高度。结果改到最后和暴力解法差不多了。

这种解法的关键是弄清楚换根之后节点高度的变化。经过分析只有换根的两个节点受到影响。分为两种情况，如果新根为旧根提供了最大高度，那么旧根应变为其邻接节点次大高度+1（第一次递归进来时计算）。如果新根没有为旧根提供最大高度，旧根高度不变仍为其邻接节点最大高度+1（第一次递归进来时计算）。新根是其邻接节点最大高度+1（这里面包括了刚才改变高度的旧根）。

注意：这里每个节点记录的是以0为根进行dfs，从叶子节点累加的高度。因此，当前节点高度就等于邻接节点最大高度加1。

代码

/**
 * @date 2024-03-17 16:04
 */
public class FindMinHeightTrees {

    public int[] res;
    public int minHeight;
    List<Integer>[] g;
    int[] dp;

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        g = new ArrayList[n];
        for (int i = 0; i < g.length; i++) {
            g[i] = new ArrayList<>();
        }
        dp = new int[n];
        res = new int[n];
        minHeight = n;
        for (int i = 0; i < edges.length; i++) {
            g[edges[i][0]].add(edges[i][1]);
            g[edges[i][1]].add(edges[i][0]);
        }
        dfs(0, 0);
        redfs(0, 0);

        List<Integer> minHeights = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (res[i] == minHeight) {
                minHeights.add(i);
            }
        }
        return minHeights;

    }

    public void redfs(int root, int parent) {
        // 进入到该层后，保存其最大与次大深度，后面换根后再回来遍历其它兄弟节点时不会受到换根影响
        // 由于是深度遍历，换根到子节点与当前根的深度有关
        // 由子节点返回后，状态已保存，不受换根影响
        int max = 0;
        int second = 0;
        for (Integer neighbor : g[root]) {
            if (dp[neighbor] > max) {
                second = max;
                max = dp[neighbor];
            } else if (dp[neighbor] > second) {
                second = dp[neighbor];
            }
        }
        // max是与root相邻节点的高度，加1才是root的最大高度
        res[root] = max + 1;
        // 更新最小高度
        minHeight = Math.min(minHeight, res[root]);
        for (Integer next : g[root]) {
            if (next == parent) {
                // 遇到叶子节点返回
                continue;
            }
            // 换到下一个根next，修改root的高度，如果下一个点为当前点提供了最大高度，那么当前节点高度为
            // 次高加一，否则是最高加一
            dp[root] = (dp[next] == max ? second : max) + 1;
            redfs(next, root);
        }
    }

    public int dfs(int root, int parent) {
        dp[root] = 1;
        for (Integer next : g[root]) {
            if (next != parent) {
                dp[root] = Math.max(dp[root], dfs(next, root) + 1);
            }
        }
        return dp[root];
    }

    public static void main(String[] args) {
        FindMinHeightTrees main = new FindMinHeightTrees();
//        System.out.println(main.findMinHeightTrees(4, new int[][]{{1, 0}, {1, 2}, {1, 3}}));
//        System.out.println(main.findMinHeightTrees(6, new int[][]{{3, 0}, {3, 1}, {3, 2}, {3, 4}, {5, 4}}));
//        System.out.println(main.findMinHeightTrees(7, new int[][]{{0, 1}, {1, 2}, {1, 3}, {2, 4}, {3, 5}, {4, 6}}));
//        System.out.println(main.findMinHeightTrees(8, new int[][]{{0,1},{1,2},{2,3},{0,4},{4,5},{4,6},{6,7}}));
        System.out.println(main.findMinHeightTrees(11, new int[][]{{0, 1}, {0, 2}, {2, 3}, {0, 4}, {2, 5}, {5, 6}, {3, 7}, {6, 8}, {8, 9}, {9, 10}}));
//        System.out.println(main.findMinHeightTrees(2, new int[][]{{0, 1}}));
    }
}

性能

目标

给你一个下标从 0 开始、由正整数组成的数组 nums 。

你可以在数组上执行下述操作 任意 次：

• 选中一个同时满足 0 <= i < nums.length - 1 和 nums[i] <= nums[i + 1] 的整数 i 。将元素 nums[i + 1] 替换为 nums[i] + nums[i + 1] ，并从数组中删除元素 nums[i] 。

返回你可以从最终数组中获得的 最大 元素的值。

示例 1：

输入：nums = [2,3,7,9,3]
输出：21
解释：我们可以在数组上执行下述操作：
- 选中 i = 0 ，得到数组 nums = [5,7,9,3] 。
- 选中 i = 1 ，得到数组 nums = [5,16,3] 。
- 选中 i = 0 ，得到数组 nums = [21,3] 。
最终数组中的最大元素是 21 。可以证明我们无法获得更大的元素。

示例 2：

输入：nums = [5,3,3]
输出：11
解释：我们可以在数组上执行下述操作：
- 选中 i = 1 ，得到数组 nums = [5,6] 。
- 选中 i = 0 ，得到数组 nums = [11] 。
最终数组中只有一个元素，即 11 。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6

思路

这个题要我们对一个数组进行操作并返回最大的元素值。这里的操作指的是合并相邻的非严格递增元素。

刚开始没有头绪，如果真的按照操作步骤先把符合条件的值求出来，替换掉较大元素的值并删掉较小元素，那么就需要频繁地移动数组数据。

除此之外需要考虑一个重要的问题，如何合并才能使最终的结果最大？如果从前向后合并，比如 [2,6,7] 先合并前两个得到[8,7]肯定没有从后向前合并得到的值 [2, 13] [15] 大。是否存在那种先从前向后合并，然后再从后向前合并才能得到最大值的情况？

刚开始是不那么容易弄清的。也考虑过优先合并 后面的元素值 比 合并后的元素值 大的 元素，提前考虑了一步能否避免上面的情况？好像可以，因为操作没有破坏原数组能否合并的状态。那么这种操作需要循环几次？时间复杂度是O(n)~O(nlogn)吗？

[1,2,1,4,1,2,1,4]一次遍历后可以变为[3,5,3,5]，然后再遍历一次得到 [8, 8]，再来一次 [16]，即O(nlogn)。更好的情况就是递增序列O(n)。

经过上面的分析可以发现，优先使后面的元素最大才能得到最大值。那么为什么不从后向前遍历并累加呢？如果遇到一个元素的值比后面所有元素的累加和还要大，那不管前面怎么操作，由于元素都是正整数，合并后只会更大。

想清楚了这一点就非常简单了。

代码

/**
 * @date 2024-03-14 11:29
 */
public class MaxArrayValue {

    public long maxArrayValue(int[] nums) {
        long res = nums[nums.length - 1];
        for (int i = nums.length - 1; i >= 1; i--) {
            res = res >= nums[i - 1] ? res + nums[i - 1] : nums[i - 1];
        }
        return res;
    }

    public static void main(String[] args) {
        MaxArrayValue main = new MaxArrayValue();
//        int[] nums = new int[]{2, 3, 7, 9, 3};
//        int[] nums = new int[]{5, 3, 3};
//        int[] nums = new int[]{77};
        int[] nums = new int[]{34, 95, 50, 12, 25, 100, 21, 3, 25, 16, 76, 73, 93, 46, 18};
        System.out.println(main.maxArrayValue(nums));
    }
}

性能

目标

给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。

你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ：

从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。
返回你在矩阵中能够 移动 的 最大 次数。

示例 1：

输入：grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
输出：3
解释：可以从单元格 (0, 0) 开始并且按下面的路径移动：
- (0, 0) -> (0, 1).
- (0, 1) -> (1, 2).
- (1, 2) -> (2, 3).
可以证明这是能够移动的最大次数。

示例 2：

输入：grid = [[3,2,4],[2,1,9],[1,1,7]]
输出：0
解释：从第一列的任一单元格开始都无法移动。

说明：

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 1000
• 4 <= m * n <= 10^5
• 1 <= grid[i][j] <= 10^6

思路

题目要我们求从矩阵第一列出发的最大移动次数。当前单元格可以移动到其后面一列的上中下三格，如果相应位置的值大于当前元素的话。

这道题可以使用动态规划来做，虽然重叠的子问题不多。从右向左，从下到上/从上到下，计算每个单元格可以移动的最大次数。然后求第一列的最大值即可。

值得注意的是这种列在外层从右向左的循环方式。如果像平时那样外层行循环内层列循环，那么写状态转移方程时，子问题可能还未计算。

官网题解给的是广度优先搜索的方法，遍历第一列起点，将能到达的第二列的格子加入集合，然后遍历这些格子，如此反复直到无法继续或者到达矩阵最大边界n-1。

代码

/**
 * @date 2024-03-16 15:08
 */
public class MaxMoves {

    public int maxMoves(int[][] grid) {
        int[][] dp = new int[grid.length][];
        for (int i = 0; i < grid.length; i++) {
            dp[i] = new int[grid[i].length];
        }
        int res = 0;
        int i = grid.length - 1;
        for (int j = grid[i].length - 2; j >= 0; j--) {
            i = grid.length - 1;
            for (; i >= 0; i--) {
                if (i != 0 && grid[i][j] < grid[i - 1][j + 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j + 1] + 1);
                }
                if (grid[i][j] < grid[i][j + 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j + 1] + 1);
                }
                if (i != grid.length - 1 && grid[i][j] < grid[i + 1][j + 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i + 1][j + 1] + 1);
                }
                if (j == 0){
                    res = Math.max(res, dp[i][0]);
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        MaxMoves main = new MaxMoves();
        System.out.println(main.maxMoves(new int[][]{{2, 4, 3, 5}, {5, 4, 9, 3}, {3, 4, 2, 11}, {10, 9, 13, 15}}));
    }
}

性能

网友的题解还有网格DFS（2ms）、BFS（6ms）。虽然时间复杂度都是O(mn)，但是性能差别还是挺大的。有时间可以分析一下，性能到底差在哪里。先不追求性能100%了，先以最快的速度将题过一遍。

目标

给出一个满足下述规则的二叉树：

1. root.val == 0
2. 如果 treeNode.val == x 且 treeNode.left != null，那么 treeNode.left.val == 2 * x + 1
3. 如果 treeNode.val == x 且 treeNode.right != null，那么 treeNode.right.val == 2 * x + 2

现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。

请你先还原二叉树，然后实现 FindElements 类：

• FindElements(TreeNode* root) 用受污染的二叉树初始化对象，你需要先把它还原。
• bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。

说明：

• TreeNode.val == -1
• 二叉树的高度不超过 20
• 节点的总数在 [1, 10^4] 之间
• 调用 find() 的总次数在 [1, 10^4] 之间
• 0 <= target <= 10^6

思路

dfs还原节点val，并将其加入到Hash表中，直接contains判断。

这个题被标为medium，估计是想让我们自己实现Hash表来查找元素吧。

代码

/**
 * @date 2024-03-12 2:41
 */
public class FindElements {
    Set<Integer> elements;

    public FindElements(TreeNode root) {
        elements = new HashSet<>();
        recover(root, 0);
    }

    public void recover(TreeNode root, int value) {
        if (root == null) {
            return;
        }
        root.val = value;
        elements.add(value);
        recover(root.left, 2 * value + 1);
        recover(root.right, 2 * value + 2);
    }

    public boolean find(int target) {
        return elements.contains(target);
    }
}

性能

目标

你在和朋友一起玩 猜数字（Bulls and Cows）游戏，该游戏规则如下：

写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：

• 猜测数字中有多少位属于数字和确切位置都猜对了（称为 "Bulls"，公牛），
• 有多少位属于数字猜对了但是位置不对（称为 "Cows"，奶牛）。也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。

给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。

提示的格式为 "xAyB" ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B 表示奶牛。

请注意秘密数字和朋友猜测的数字都可能含有重复数字。

示例 1：

输入：secret = "1807", guess = "7810"
输出："1A3B"
解释：数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
"1807"
  |
"7810"

示例 2：

输入：secret = "1123", guess = "0111"
输出："1A1B"
解释：数字和位置都对（公牛）用 '|' 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
"1123"        "1123"
  |      or     |
"0111"        "0111"
注意，两个不匹配的 1 中，只有一个会算作奶牛（数字猜对位置不对）。通过重新排列非公牛数字，其中仅有一个 1 可以成为公牛数字。

说明：

• 1 <= secret.length, guess.length <= 1000
• secret.length == guess.length
• secret 和 guess 仅由数字组成

思路

这个题目的算法还是挺直接的，就是比较相应位置上的数字是否一致，如果一致bulls加1，否则就要累加错误数字的出现次数，但最多不能超过其在secret中的个数。

代码

/**
 * @date 2024-03-10 0:36
 */
public class GetHint {
    public String getHint(String secret, String guess) {
        int bulls = 0;
        int cows = 0;
        char[] secretCharArray = secret.toCharArray();
        int[] missArray = new int[10];
        int[] cowsArray = new int[10];
        for (int i = 0; i < secretCharArray.length; i++) {
            int guessCharacter = guess.charAt(i) - '0';
            int secretCharacter = secretCharArray[i] - '0';
            if (guessCharacter == secretCharacter) {
                bulls++;
            } else {
                missArray[secretCharacter] += 1;
                cowsArray[guessCharacter] += 1;
            }
        }
        for (int i = 0; i < cowsArray.length; i++) {
            if (missArray[i] > 0 && cowsArray[i] > 0) {
                cows += Math.min(missArray[i], cowsArray[i]);
            }
        }
        StringBuilder sb = new StringBuilder();
        return sb.append(bulls).append('A').append(cows).append('B').toString();
    }
}

这里面有几点需要注意：

1. 数组只需要保留0-9十个数字即可
2. 数字字符减去'0'可以得到对应的整型数字
3. 不要使用加号拼接返回的结果，因为每一次字符串的修改都会创建新的对象，会显著影响性能

性能

目标

给你两个正整数：n 和 target 。

如果数组 nums 满足下述条件，则称其为 美丽数组 。

• nums.length == n.
• nums 由两两互不相同的正整数组成。
• 在范围 [0, n-1] 内，不存在 两个 不同 下标 i 和 j ，使得 nums[i] + nums[j] == target 。

返回符合条件的美丽数组所可能具备的 最小 和，并对结果进行取模 10^9 + 7。

示例 1：

输入：n = 2, target = 3
输出：4
解释：nums = [1,3] 是美丽数组。
- nums 的长度为 n = 2 。
- nums 由两两互不相同的正整数组成。
- 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。
可以证明 4 是符合条件的美丽数组所可能具备的最小和。

示例 2：

输入：n = 3, target = 3
输出：8
解释：
nums = [1,3,4] 是美丽数组。 
- nums 的长度为 n = 3 。 
- nums 由两两互不相同的正整数组成。 
- 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。
可以证明 8 是符合条件的美丽数组所可能具备的最小和。

示例 3：

输入：n = 1, target = 1
输出：1
解释：nums = [1] 是美丽数组。

说明：

• 1 <= n <= 10*9
• 1 <= target <= 10^9

思路

首先，美丽数组一个长度为n的数组，数组中的元素均不相同且为正整数，且任意两个元素之后不能等于target。

我们需要寻找所有可能的美丽数组中，所有元素和最小的那一个。并返回这个最小和。

如何才能使元素和最小？

很明显应该是从1开始的正整数序列，但是这个序列中的值相加不能等于target。

那么本质上是要求 1______mid~~~~~~target______这一序列的值，其中~~~~~~区间的值应舍去，因为会与前面的相加得到target。

刚开始想的是循环遍历 [1, n) 累加和，并记录target - i，如果遍历的过程中遇到了就直接跳过，但是提交后提示超出内存限制。于是进行修改，不保存不符合条件的元素，直接根据下标来判断，这次提示超时。

然后尝试不使用循环，直接使用等差数列求和公式计算，结果整型溢出。需要注意运算符优先级高的会先计算，如果没有显式地类型转换就会溢出，并且隐式类型转化使用的是溢出后的值。

代码

/**
 * @date 2024-03-08 9:00
 */
public class MinimumPossibleSum {

    public final int MOD = 1000000007;

    public int minimumPossibleSum(int n, int target) {
        int mid;
        mid = target / 2;
        if (n <= mid) {
            return (int) ((n + n * (n - 1L) / 2L) % MOD);
        } else {
            int r = n - mid;
            return (int) (((mid + mid * (mid - 1L) / 2L) + (long) target * r + r * (r - 1L) / 2L) % MOD);
        }
    }
}

性能

给你一个下标从 0 开始的字符串 word ，长度为 n ，由从 0 到 9 的数字组成。另给你一个正整数 m 。

word 的 可整除数组 div 是一个长度为 n 的整数数组，并满足：

• 如果 word[0,...,i] 所表示的 数值 能被 m 整除，div[i] = 1
• 否则，div[i] = 0
• 返回 word 的可整除数组。

示例 1：

输入：word = "998244353", m = 3
输出：[1,1,0,0,0,1,1,0,0]
解释：仅有 4 个前缀可以被 3 整除："9"、"99"、"998244" 和 "9982443" 。

示例 2：

输入：word = "1010", m = 10
输出：[0,1,0,1]
解释：仅有 2 个前缀可以被 10 整除："10" 和 "1010" 。

说明：

• 1 <= n <= 10^5
• word.length == n
• word 由数字 0 到 9 组成
• 1 <= m <= 10^9

思路

题目要求的是从字符串第一个数字开始，验证数字能否被给定的正整数m整除。很容易想到的方法是创建一个StringBuilder，遍历字符串的Character，依次加入StringBuilder，然后转化为数字，求余判断能否整除。提交运行发现会溢出，虽然word的最大长度为10^5，但是Long的最大值也才 9223372036854775807 共19位，直接求解行不通。

很自然地想到需要分治处理，比方说先在Long的范围内算，每次处理19位，然后记录余数，再接上后面的18位。但是感觉这样具体实现起来很别扭，实际上求余数的时候也没必要每次都从头开始。

因此，我们可以用每一位对m（它不超过10^9，在Integer 2147483647 的范围内）进行MOD运算，同时记录结果。如果为0，则将输出数组中的相应位置赋值为1，否则为0。然后将余数 remainder * 10加上下一位字符所示的数字，再进行MOD运算以此类推即可。

代码

/**
 * @date 2024-03-07 9:27
 */
public class DivisibilityArray {
    public int[] divisibilityArray(String word, int m) {
        long remainder = 0;
        int n = word.length();
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            remainder = (remainder * 10 + (word.charAt(i) - '0')) % m;
            if (remainder == 0) {
                res[i] = 1;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        DivisibilityArray main = new DivisibilityArray();
        String str = "1000000000100000000030199999999610000000009199999999079999999938299999999010000000009999999991100000000010000000001000000000100000000071999999992100000000010000000003099999999759999999951000000000100000000010000000001000000000822999999988269999999921000000000100000000010000000005999999995900999999991100000000069999999947445979999999641999999999059999999957999999993100000000080609999999868999999992599999999867999999993100000000";
        int m = 1000000000;
        main.divisibilityArray(str, m);
    }
}

这里面有个小技巧，就是使用 Character - '0'来得到相应的数字，Character.getNumericValue考虑的情况比较多，这里用不到。同时需要注意，余数应使用long类型防止整数溢出。

性能

目标

给你一个整数 n 表示一棵 满二叉树 里面节点的数目，节点编号从 1 到 n 。根节点编号为 1 ，树中每个非叶子节点 i 都有两个孩子，分别是左孩子 2 i 和右孩子 2 i + 1 。

树中每个节点都有一个值，用下标从 0 开始、长度为 n 的整数数组 cost 表示，其中 cost[i] 是第 i + 1 个节点的值。每次操作，你可以将树中 任意 节点的值 增加 1 。你可以执行操作 任意 次。

你的目标是让根到每一个 叶子结点 的路径值相等。请你返回 最少 需要执行增加操作多少次。

注意：

• 满二叉树 指的是一棵树，它满足树中除了叶子节点外每个节点都恰好有 2 个子节点，且所有叶子节点距离根节点距离相同。
• 路径值 指的是路径上所有节点的值之和。

说明：

• 3 <= n <= 105
• n + 1 是 2 的幂
• cost.length == n
• 1 <= cost[i] <= 104

思路

操作首先要知道操作的最终状态：各路径相等。那么哪一个路径值可以使操作总数最小？既然明确不了哪一个路径又如何操作，又怎会知道最小？最开始以为可能是路径的中位数，但是我也没法证明。后来发现想复杂了，操作只能加不能减，那么问题就变成了将所有路径变成最大最少需要几次操作。

首先可以根据节点的父子关系将子路径值层层累加，那么最底下的叶子层就是各条路径的值。用最大路径值分别减去其它路径值得到相应的操作数，但这时操作数不是最小的。注意到，如果左右孩子所需操作均不为零，可以将较小孩子节点的操作数提到父节点上，并将操作数置零，而另一个孩子节点同时减去该操作数，这样就完成了一步最小化。依次向上计算，直到根节点，然后统计各节点操作数即可。

代码

/**
 * @date 2024-02-28 8:52
 */
public class MinIncrements {

    public int minIncrements(int n, int[] cost) {
        for (int i = 1; i < cost.length; i++) {
            if (i % 2 == 1) {
                cost[i] += cost[(i - 1) / 2];
            } else {
                cost[i] += cost[(i - 2) / 2];
            }
        }
        int max = 0;
        double l = Math.floor(Math.log(Double.parseDouble(String.valueOf(n))) / Math.log(2.0));
        for (int i = (int) Math.pow(2.0, l) - 1; i < cost.length; i++) {
            if (cost[i] > max) {
                max = cost[i];
            }
        }
        for (int i = (int) Math.pow(2.0, l) - 1; i < cost.length; i++) {
            cost[i] = max - cost[i];
        }
        for (int i = cost.length - 1; i > 2; i -= 2) {
            if (cost[i] == 0 || cost[i - 1] == 0) {
                cost[(i - 2) / 2] = 0;
                continue;
            }
            if (cost[i] <= cost[i - 1]) {
                cost[(i - 2) / 2] = cost[i];
                cost[i - 1] = cost[i - 1] - cost[i];
                cost[i] = 0;
            } else if (cost[i] >= cost[i - 1]) {
                cost[(i - 2) / 2] = cost[i - 1];
                cost[i] = cost[i] - cost[i - 1];
                cost[i - 1] = 0;
            }
        }
        int res = 0;
        for (int i = 1; i < cost.length; i++) {
            res += cost[i];
        }
        return res;
    }

    public static void main(String[] args) {

        MinIncrements main = new MinIncrements();
//        int[] cost = new int[]{1, 5, 2, 2, 3, 3, 1};
        int[] cost = new int[]{764, 1460, 2664, 764, 2725, 4556, 5305, 8829, 5064, 5929, 7660, 6321, 4830, 7055, 3761};
        System.out.println(main.minIncrements(cost.length, cost));
    }
}

性能

又是勉强过关。看看官网给的答案：

class Solution {
    public int minIncrements(int n, int[] cost) {
        int ans = 0;
        for (int i = n - 2; i > 0; i -= 2) {
            ans += Math.abs(cost[i] - cost[i + 1]);
            // 叶节点 i 和 i+1 的双亲节点下标为 i/2（整数除法）
            cost[i / 2] += Math.max(cost[i], cost[i + 1]);
        }
        return ans;
    }
}

称之为自底向上的贪心算法。所谓贪心算法，它在每一步都做出当时看起来最佳的选择，也就是说，它总是做出局部最优的选择。贪心算法并不保证得到最优解，但对很多问题确实可以求得最优解。

目标

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

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

思路

我第一次想到的方法是先找到这两个指定节点，然后交替求取位置索引较大节点的父节点。然后比较，如果值相等则为公共祖先。但是，题目给出的树结构中不包含指向父节点的引用，很自然地想到先将值保存到数组中，中序遍历二叉搜索树得到正序序列。然后二分查找出index，计算父节点index：左孩是奇数index，父index为(child-1)/2，右孩是偶数index，父index为(child-2)/2，注意排除root，index为0。接着比较父节点的值，还应该考虑输入节点本身就是父子关系的情况，如果pindex > qindex，应先求p节点的父index，因为index大，层数可能更高。再与qindex对应的值比较，不相等的话再求q节点的父index，依此类推。题目中有提到，树中的值都是唯一的。这个想法看起来正确，但真正去实现的时候就会发现是不可行的。首先是存储空间问题，要在数组中保留树的结构，在有许多空节点的情况下是不可行的。这个在 二叉搜索树最近节点查询 中提到过。然后是二分查找需要先排序的问题，这本身就打乱了树节点的index关系。

这几天刷题有一个感受，就是如果算法实现起来太过复杂那么一定是有问题的，很有可能是求解的方向不对。

于是我换了一种思路，还是先找到这两个节点，但是在找的过程中记录下访问的路径，然后再找到路径节点中所有相同节点中的最后一个即可。那么路径应该保存到哪里，又如何获取相同节点序列的最后一个呢？

在 Java 的标准库中，java.util.Stack 类是使用数组实现的。然而，从 Java 6 开始，java.util.Stack 类被标记为遗留（legacy），并建议使用 java.util.Deque 接口及其实现（如 ArrayDeque 或 LinkedList）来替代。Deque 接口表示双端队列，它支持在两端插入和删除元素，因此非常适合实现栈和队列。----AI的回答

无论是使用数组还是链表，最后查找的时候，都可以从头开始同时比较，直到第一个不相等节点出现即可。无需额外申请空间。

如果从尾开始比较的话，需要借助HashSet，将其中一个路径序列存入集合，然后循环弹另一个路径栈，第一个在集合中的被弹出元素就是最近的公共祖先。需要额外的空间。有的时候条件反转一下可以简化处理逻辑，而有时则相反！

另外数组长度固定，超过的话就会有重新分配空间的开销。

代码

public TreeNode lowestCommonAncestor_v1(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> pStack = findPath(root, p.val, new Stack<>());
        Stack<TreeNode> qStack = findPath(root, q.val, new Stack<>());
        HashSet<Integer> set = new HashSet<>();
        while (!pStack.empty()){
            set.add(pStack.pop().val);
        }
        TreeNode res = null;
        while (!qStack.empty()){
            res = qStack.pop();
            if (set.contains(res.val)) {
                break;
            }
        }
        return res;
    }

public Stack<TreeNode> findPath(TreeNode subRoot, int value, Stack<TreeNode> stack) {
    stack.push(subRoot);
    if (subRoot.val == value) {
        return stack;
    } else if (subRoot.val > value) {
        return findPath(subRoot.left, value, stack);
    } else {
        return findPath(subRoot.right, value, stack);
    }
}

/**
 * 还有一个更好的做法是一次遍历同时比较p,q，如果一个大于等于，一个小于等于 当前节点值，表明已经/准备分叉了
 * 这个是看了题解之后发现的
 */
public TreeNode lowestCommonAncestor_v2(TreeNode root, TreeNode p, TreeNode q) {
    if (root.val > p.val && root.val > q.val) {
        return lowestCommonAncestor_v2(root.left, p, q);
    } else if (root.val < p.val && root.val < q.val) {
        return lowestCommonAncestor_v2(root.right, p, q);
    } else {
        return root;
    }
}

性能