首页 > 代码库 > 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; }
本代码只代表个人观点,如有错误,请指正,谢谢
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。