2ms Java AC O(n) solution

  • 5

    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.

    public class Solution {
        public int rob(TreeNode root) {
            return robHelp(root).x;
        public Point robHelp(TreeNode root) {
            if (root == null) {
                return new Point(0, 0);
            Point leftPoint = robHelp(root.left);
            Point rightPoint = robHelp(root.right);
            return new Point(Math.max(root.val + leftPoint.y + rightPoint.y, leftPoint.x + rightPoint.x), leftPoint.x + rightPoint.x);

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.