import levelTravel429.Node;

import java.util.*;

public class LeetCode_337_28 {



    public int rob(TreeNode root) {
        if(root==null){
            return 0;
        }
        Map<TreeNode,Integer> map=new HashMap<TreeNode,Integer>();
        return dp(root,map);

    }

    public Integer dp(TreeNode node,Map<TreeNode,Integer> map){
        if (node==null){
            return 0;
        }
        if(!map.containsKey(node) ){
            int left=dp(node.left,map);
            int right=dp(node.right,map);
            int left_left=(node.left==null? 0:dp(node.left.left,map));
            int left_right=(node.left==null? 0:dp(node.left.right,map));
            int right_left=(node.right==null? 0:dp(node.right.left,map));
            int right_right=(node.right==null? 0:dp(node.right.right,map));
            map.put(node,Math.max(Math.max(Math.max(left+right,
                    (node.left==null? 0:node.left.val)+right_left+right_right),
                    (node.right==null? 0:node.right.val)+left_left+left_right),
                    node.val+left_left+left_right+right_left+right_right));
        }
        System.out.println(map.get(node));
        return map.get(node);
    }

    public static void main(String[] args) {
        TreeNode root=new TreeNode(1);
        root.left=new TreeNode(2);
        root.right=new TreeNode(3);
        System.out.println(new LeetCode_337_28().rob(root));
    }
}