福州官网建站厂,在ps做网站分辨率96可以吗,泉州建设网站,网站营销推广如何做问题描述#xff1a;在上次大街万一条街道之后和一圈房屋后#xff0c;小偷又发现了一个新的可行窃的地区。这个地区只有一个入口#xff0c;我们称之为根。除了根之外#xff0c;每栋房子有且只有一个父房子与之项链#xff0c;一番侦查之后#xff0c;聪明的小偷意识到…问题描述在上次大街万一条街道之后和一圈房屋后小偷又发现了一个新的可行窃的地区。这个地区只有一个入口我们称之为根。除了根之外每栋房子有且只有一个父房子与之项链一番侦查之后聪明的小偷意识到这个地方的所有房屋的排列类似于一颗二叉树如果两个直接项链的房子在同一天北大街房屋将自动报警计算在不触动警报的情况下小偷一晚上能够盗取的最高金额
递归求解分析采用一个参数表征父节点是否选取若没有偷父节点则子节点有选和不选两种情况若偷了父节点则只能不选该节点最后比较选根节点和不选根结点的最大值返回
private int maxProfit(TreeNode node,int ischooseparent)
{
//如果当前节点为null则返回0
if(nodenull)
{
return 0;
}
//如果选择了父节点则当前节点不能选择只能向下选择
if(ischooseparent)
{
return maxProfit(node.left,false)maxProfit(node.left,false);
}
else
{
//没有的话可以选择父节点和不选择父节点两种情况并取最大值返回
return Math.max(node.valmaxProfit(node.left,true)maxProfit(node.right,false),maxProfit(node.left,false)maxProfit(node.left,false))
}
}public int MaxProfit(TreeNode node )
{
//从根节点开始递归遍历且在这之前没有选择根结点的父节点从而传值为false
return maxProfit(node,false);
}
