首页 > 代码库 > LIS问题分析

LIS问题分析

题目来源,待字闺中,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”

原题这个LIS问题,可不是Longest Increasing Subsequence,而是Largest Independent Set,含义如下:给定一棵二叉树,找到满足如下条件的最大节点集合:集合中的任意两个节点之间,都没有边。如下图:


LIS大小为5,为{10,40,60,70,80}.

分析:首先还是递归思想,比如对于根节点10,如果把10放入LIS则,20和30不能放入,但它们的孩子40、50、60可以;如果不把10放入,则它的孩子20和30可以,如此可得递归方程式为

fun(root)=max(fun(root->left)+fun(root->right),1+fun(root->left->left)+fun(root->left->right)+fun(root->right->left)+fun(root->right->right));同样,由于存在重复子问题,因此可以考虑动态规划,但是对于树来说,动态规划需要特殊处理,因为我们没办法从下往上进行处理,这里有一个技巧,我们可以给树节点添加一个标志lis,当该节点没有访问时lis初始化为0,访问后lis保存为当前节点的lis集合的大小,从而可以避免重复递归,具体见代码:

struct BinaryTreeNode
{
	int data;
	int lis;//表示以当前节点为根时lis集合的大小,初始化为0,可以防止重复递归
	BinaryTreeNode* left;
	BinaryTreeNode* right;
	BinaryTreeNode(int val):data(val),lis(0),left(NULL),right(NULL){}
};

int LIS(BinaryTreeNode* root)
{
	if(root == NULL)return 0;
	if(root->lis)return root->lis;
	int numNotContainRoot = LIS(root->left)+LIS(root->right);//根节点不加入lis
	int numContatinRoot = 1;//根节点加入lis
	if(root->left) numContatinRoot+=LIS(root->left->left)+LIS(root->left->right);
	if(root->right)numContatinRoot+=LIS(root->right->left)+LIS(root->right->right);
	root ->lis = max(numNotContainRoot,numContatinRoot);//保存当前根节点所在子树的lis大小
	return root->lis;
}

本代码只代表个人观点,如有错误,请指正,谢谢