377.md

Palindromic Substrings

题目

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.

Example 1: Input: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

Output: 7 Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2: Input: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

Output: 9 Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9. 思路

总结：
	
    root
    / \
   y   z

如果偷取root结点的钱，那么加上y子树不偷取y的根节点最大值和z子树不偷取z的根节点最大值即为 偷取root的最大值。
如果不偷取root的结点的钱，那么最大值为y子树的最大值加上z子树的最大值(并不一定需要y,z的根节点)。

代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rob(root *TreeNode) int {
    robRoot, noRoot := dfs(root)
    return max(robRoot, noRoot)
}

func dfs(node * TreeNode) (int, int) {
    if node == nil {
        return 0, 0   
    }
    leftRobRoot, leftNoRoot := dfs(node.Left)
    rightRobRoot, rightNoRoot := dfs(node.Right)
    robRoot := node.Val + leftNoRoot + rightNoRoot
    noRoot := max(rightRobRoot, rightNoRoot) + max(leftRobRoot, leftNoRoot)
    //fmt.Println(node.Val,robRoot, noRoot)
    return robRoot, noRoot
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}