2ms Java AC O(n) solution
The idea is for each node, we have a associated Point. Point's x represents the MAX value for taking this node. Point's y is the MAX value for not taking this n
The idea is for each node, we have a associated Point. Point's x represents the MAX value for taking this node. Point's y is the MAX value for not taking this node. The program will go from bottom to top and keep updating until root. \n\n\n    public class Solution {\n        public int rob(TreeNode root) {\n            return robHelp(root).x;\n        }\n        public Point robHelp(TreeNode root) {\n            if (root == null) {\n                return new Point(0, 0);\n            }\n            Point leftPoint = robHelp(root.left);\n            Point rightPoint = robHelp(root.right);\n            \n            return new Point(Math.max(root.val + leftPoint.y + rightPoint.y, leftPoint.x + rightPoint.x), leftPoint.x + rightPoint.x);\n        }\n    }
[]