老师讲这是树形dp的入门题目 解题思路是以二叉树的遍历（递归三部曲）再结合动规五部曲 dp数组如何定义：只需要定义一个二个元素的数组，dp[0]与dp[1] dp[0]表示不偷当前节点的最大价值dp[1]表示偷当前节点后的最大价值这样可以把每个节点的状态值都表示出来 但这个数组的两个值只表示当前节点的状态值 递归时要使用后序遍历： 使用后序遍历的原因就是要从叶子结点一层一层向上统计出来
class Solution {
private : int * binaryTreeRob ( TreeNode* node) { if ( node == nullptr ) { return new int [ 2 ] { 0 , 0 } ; } int * parr = new int [ 2 ] { 0 , 0 } ; int * p_left = binaryTreeRob ( node-> left) ; int * p_right = binaryTreeRob ( node-> right) ; parr[ 1 ] = node-> val + p_left[ 0 ] + p_right[ 0 ] ; parr[ 0 ] = std:: max ( p_left[ 0 ] , p_left[ 1 ] ) + std:: max ( p_right[ 0 ] , p_right[ 1 ] ) ; return parr; }
public : int rob ( TreeNode* root) { int * arr = binaryTreeRob ( root) ; return std:: max ( arr[ 0 ] , arr[ 1 ] ) ; }
} ;
