My exponential solution got TLE, anyone can hint a dp solution?


  • -1
    C
    public int RobIII(TreeNode root)
        {
            if (root == null) return 0;
            int max  = Math.Max(RobIII(root, true), RobIII(root, false));
            return max;
        }
    
        private int RobIII(TreeNode root, bool canrob)
        {
            if (root == null) return 0;
            if (canrob)
            {
                return Math.Max(RobIII(root.left, false) + RobIII(root.right, false) + root.val, RobIII(root.left, true) + RobIII(root.right, true) );
          
            }
            else { 
                return RobIII(root.left, true) + RobIII(root.right, true);
          
            }
        }

  • 0
    C

    I came up with this bottom-up O(n) solution but the mock interview ended :(

    public int RobIII(TreeNode root)
        {
            int[] result = HelperRobIII(root);
            return Math.Max(result[0], result[1]);
        }
    
        private int[] HelperRobIII(TreeNode root)
        { // int[]{sum, robbed}
            if (root == null) return null;
            int[] left = HelperRobIII(root.left);
            int[] right = HelperRobIII(root.right);
            if (left == null && right == null) return new int[] { root.val, 0 };
            else if (left != null && right == null) {
                int max = Math.Max(root.val + left[1], left[0]);
                return new int[] { max, left[0] };
            }
            else if (right != null && left == null)
            {
                int max = Math.Max(root.val + right[1], right[0]);
                return new int[] { max, right[0] };
            }
            else {
                int max = Math.Max(left[0] + right[0], root.val + left[1] + right[1]);
                return new int[] { max, left[0] + right[0] };
            }
        }

Log in to reply
 

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