Simple solution with postorder tree traversal


  • 0
    S
        public int rob(TreeNode root) {
            int[] result = helper(root);
            return Math.max(result[0], result[1]);
        }
        
        private int[] helper(TreeNode root) {
            int[]  result = new int[2];
            if(root != null) {
                int[] left = helper(root.left);
                int[] right = helper(root.right);
                
                //Do not include the root
                result[0] = Math.max(left[0], left[1]) + 
                Math.max(right[0], right[1]);
    
                // Solution with the root
                result[1] = left[0] + right[0];
                result[1] += root.val;
            }
            return result;
        }

Log in to reply
 

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