Java 中的最大独立集

给出了一个二叉树。我们的任务是找到给定二叉树的最大独立集的大小。二叉树的独立集仅包含二叉树中不直接相互连接的那些节点。换句话说，对于集合中的任何两个节点，它们之间至少要有一个节点。

示例

输入

对于下面的二叉树

最大的独立集是 {100, 400, 600, 700, 800}，因为这些节点不相邻。其大小为 5。因此，输出为 5。

方法：使用递归

方法很简单。给定的二叉树的节点可以包含在解决方案中，也可以不包含在解决方案中。我们可以基于这两个条件进行递归调用。一次递归调用包含该节点，另一次递归调用则排除该节点。以下实现展示了这一点。

文件名： LIS.java

输出

The size of the Largest Independent Set is: 5

复杂度分析：在上述程序中，每次递归调用都会导致两个递归调用（一次用于排除，一次用于包含解决方案中的元素）。因此，程序的时间复杂度为 O(2ⁿ)，其中 n 是二叉树中存在的总节点数。请注意，这是指数时间复杂度。

程序的 time complexity 非常高，因为它是指数级的。因此，对于处理更大的输入，上述程序并不适用，因此需要进行一些优化。

方法：使用带备忘录的递归

上述程序反复计算许多子问题，这导致了更高的 time complexity。例如，值为 500 的节点会针对值为 100 和 200 的节点进行计算，其中值为 500 的节点是值为 100 的节点的孙节点，也是值为 200 的节点的子节点。因此，我们需要自底向上地构建解决方案，并存储子问题的解决方案，以便不必一遍又一遍地计算它们。

让我们观察上述程序的修改形式。

文件名： LIS1.java

输出

The size of the Largest Independent Set is: 5

复杂度分析：由于备忘录，程序的 time complexity 为 O(n)，其中 n 是二叉树中存在的总节点数。