LeetCode337. 打家劫舍 III

思路

实现要后序遍历二叉树。这个是树形动态规划

递归五部曲

1.定义dp数组

dp[i]:是一个二维数组。dp[0]表示取当前节点后的最大值，dp[1]表示不取当前节点，取其子节点后的最大值。

2.递推公式

 res[1]=temp.val + left[0] + right[0]; res[0]=Math.max(left[0],left[1]) + Math.max(right[0],right[1]);

3.初始化

由递推公式可以知道，需要有left数组和right数组的值。所以初始化就是递归后序遍历二叉树得到left和right数组。

4.遍历顺序

递归遍历。记得递归的结束条件。

5.打印dp数组

dp数组的dp[0]和dp[1]的最大值。

代码

/ * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode() {} *     TreeNode(int val) { this.val = val; } *     TreeNode(int val, TreeNode left, TreeNode right) { *  this.val = val; *  this.left = left; *  this.right = right; *     } * } */class Solution {    public int rob(TreeNode root) { int dp[] = robSub(root); return Math.max(dp[0],dp[1]);    }    private int[] robSub(TreeNode temp){ if(temp == null)     return new int[]{0,0}; int [] left = robSub(temp.left);  int [] right = robSub(temp.right); int res[] = new int[2]; res[1]=temp.val + left[0] + right[0]; res[0]=Math.max(left[0],left[1]) + Math.max(right[0],right[1]); return res;    }    }