题目
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.
题意
就是在一颗二叉树中，求出节点不直接相连的情况下，所能求得的节点最大和。比如计算了父节点，那么子节点就要跳过，因为他们直接相连。
例子
Input: [3,4,5,1,3,null,1]
3
/ \
4 5
/ \ \
1 3 1
题解
不直接相连求最大值的情况，除了每一层都间隔一层的情况，还有可能间隔多层计算得出最大值的，以及同一层中，可能左子结点间隔了。而右子节点不间隔的情况。所以对二叉树进行递归，左右子树都会返回两个值，
一个是包含子节点的情况下求得的最大值，一个是不包含子节点的情况下求得的最大值。而当前节点也返回两个值，当不包含当前节点时，那么下一层可包含也可不包含子节点，所以就需要求得左右子节点在包含与不包含的情况下相加所得的最大值，就左包含+右包含，左包含+右不包含，左不包含+右包含，左不包含+右不包含中的最大值，作为不包含当前节点所得的最大值；
另外一个就是包含当前节点，返回当前节点值+左右不包含的最大值。
代码
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rob(root *TreeNode) int {
HaveRoot,NoRoot := retRob(root)
if HaveRoot>NoRoot{
return HaveRoot
}
return NoRoot
}
//返回两个数，左边的数为包含root的情况下返回的最大值，右边为不包含root时返回的最大值
func retRob(root *TreeNode) (int,int){
if root==nil{
return 0,0
}
HaveRoot,NoRoot :=0,0
LHaveRoot,LNoRoot:= retRob(root.Left)
RHaveRoot,RNoRoot:= retRob(root.Right)
M1 := Max(LHaveRoot+RHaveRoot,LHaveRoot+RNoRoot)
M2 := Max(LNoRoot+RHaveRoot,LNoRoot+RNoRoot)
max := Max(M1,M2)
NoRoot = max
HaveRoot += LNoRoot+RNoRoot+root.Val
return HaveRoot,NoRoot
}
func Max(m1,m2 int)int{
if m1>m2{
return m1
}
return m2
}
总结
题目总的来说并不难，一开始便想到了递归返回两个值得情况，只是一开始并没有考虑间隔多层，以及左右子节点可以不同时包含于不包含的。区别就在于求不包含当前节点的情况，求最大值的情况，这里就是求左右包含于不包含四种情况下的最大值。
