C# In-Place DP Solution (Beats 100%)


  • 0
    K

    For each node, we have 2 choices: rob or not rob. We need to keep track of either case. Each frame will return an array where the 0th index refers to no rob, and 1st index refers to rob. After recurring into the left and right nodes, the rob case means we take the current node's value, and the no rob values of the recursive calls.
    The no rob case means we take the max of the rob and no rob case for the recursive calls, same for right.

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     public int val;
     *     public TreeNode left;
     *     public TreeNode right;
     *     public TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        
        public int Rob(TreeNode root) {
            int[] arr = Helper(root);
            return Math.Max(arr[0], arr[1]);
        }
        
        private int[] Helper(TreeNode node) {
            if(node == null){
                return new int[2];
            }
            
            int[] left = Helper(node.left);
            int[] right = Helper(node.right);
            int[] res = new int[2];
            
            res[0] = Math.Max(left[0], left[1]) + Math.Max(right[0], right[1]);
            res[1] = node.val + left[0] + right[0];
    
            
            return res;
        }
    }
    

Log in to reply
 

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