Leetcode337:打家劫舍三（！！！树型动态规划！！！）

总结树的三种遍历：

 1 //先序遍历
 2     void PreOrder(TreeNode root) {
 3         if(root == null){
 4             return;
 5         }
 6         System.out.println("树的先序遍历：执行对根节点的操作");
 7         PreOrder(root.left);
 8         PreOrder(root.right);
 9     }
10 
11     //中序遍历
12     void Inthread(TreeNode root) {
13         if(root == null){
14             return;
15         }
16         Inthread(root.left);
17         System.out.println("树的中序遍历：执行对根节点的操作");
18         Inthread(root.right);
19     }
20 
21     //后序遍历
22     void PostOrder(TreeNode root) {
23         if(root == null){
24             return;
25         }
26         PostOrder(root.left);
27         PostOrder(root.right);
28         System.out.println("树的后序遍历：执行对根节点的操作");
29     }

337. 打家劫舍 III

 维护两个动态规划表f(node) 和g(node)，其中f(node)表示偷node节点可以获得的最大金额，g(node)表示不偷node节点可以获得的最大金额

则如果偷node节点，则最大金额等于不偷node.left和不偷node.right可获得的最大金额之和，即f(node)=g(node.left)+g(node.right);

如果不偷node节点，则最大金额等于左子树的最大金额和右子树的最大金额之和，左子树的最大金额等于max(f(node.left),g(node.left))，右子树的最大金额等于max(f(node.right), g(node.right))，因此g(node) = max(f(node.left),g(node.left)) + max(f(node.right), g(node.right))

最后整棵树可获得的最大金额等于max(f(root),g(root))

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode() {}
 8  *     TreeNode(int val) { this.val = val; }
 9  *     TreeNode(int val, TreeNode left, TreeNode right) {
10  *         this.val = val;
11  *         this.left = left;
12  *         this.right = right;
13  *     }
14  * }
15  */
16 class Solution {
17     Map f = new HashMap(); //表示偷当前节点TreeNode，可以获得的最大金额Integer
18     Map g = new HashMap();//表示不偷当前节点TreeNode，可以获得的最大金额Integer
19 
20     //主方法
21     public int rob(TreeNode root) {
22         //后续遍历这棵树，填写两个表格
23         dfs(root);
24         //最后整棵树可获得的最大金额等于max(f(root),g(root))
25         return Math.max(f.getOrDefault(root,0), g.getOrDefault(root,0));
26     }
27 
28     //树的深度遍历，在遍历过程中，填动态规划的表f和g
29     public void dfs(TreeNode root){
30         if(root == null){
31             return;
32         }
33         dfs(root.left);
34         dfs(root.right);
35         //填两个表
36         f.put(root,root.val + g.getOrDefault(root.left, 0) + g.getOrDefault(root.right, 0));//偷当前节点
37         g.put(root,Math.max(f.getOrDefault(root.left,0), g.getOrDefault(root.left,0)) + Math.max(f.getOrDefault(root.right,0), g.getOrDefault(root.right,0)));//不偷当前节点
38     }
39 }