題目
https://www.geeksforgeeks.org/largest-independent-set-problem-dp-26/
給一個binary tree兜辞，我們定義non-connected set是指互不直接相連的node的集合桐猬，求這種non-connected set最多有幾個node绅这。
例子
10
/ \
20 30
/ \ \
40 50 60
/ \
70 80
Largest non-connected set in the binary tree. A subset of all tree nodes is an independent set if there is no edge between any two nodes of the subset.
Non-connected set:
- |10, 40, 50, 60| = 4
- |10, 40, 70, 80, 60| = <--- largest non-connected set
- |20, 30, 70, 80| = 4
{10, 40, 60, 70, 80} and size is 5.
解法
public class Solution {
public int lisp(Node root) {
int[] candidates = findLiss(root);
return Math.max(candidates[0], candidates[1]);
}
private int[] findLiss(TreeNode node) {
int[] size = new int[2]; // size[0]表示exclude，size[1]表示include
if (root == null) {
return new int[2];
}
int[] left = findLiss(root.left);
int[] right = findLiss(root.right);
size[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
size[1] = 1 + left[0] + right[0];
return size;
}
}
類似題目
LeetCode 337 House Robber III
https://leetcode.com/problems/house-robber-iii/
