Easy to understand, java solution


  • 1
    W
    public int rob(TreeNode root) {
        if (root == null) return 0;
        ResultSet result = DFS(root);
        return Math.max(result.preYes, result.preNo);
    }
    
    private ResultSet DFS(TreeNode root) {
        if (root.left == null && root.right == null) return new ResultSet(root.val, 0);
        
        ResultSet leftResult = new ResultSet(0, 0);
        ResultSet rightResult = new ResultSet(0, 0);
        
        if (root.left != null) {
            leftResult = DFS(root.left);
        }
        
        if (root.right != null) {
            rightResult = DFS(root.right);
        }
        
        int curYes = leftResult.preNo + rightResult.preNo + root.val;
        int curNo = Math.max(leftResult.preNo, leftResult.preYes) + Math.max(rightResult.preNo, rightResult.preYes);
        
        return new ResultSet(curYes, curNo);
    }
    
    public class ResultSet {
        int preYes;
        int preNo;
        public ResultSet (int preYes, int preNo) {
            this.preYes = preYes;
            this.preNo = preNo;
        }
    }
    

    the concept here is pretty much the same as house-robber i, in house-robber we maintain two variables, preYes and preNo to keep track of the previous optimal solution. Now in this binary tree version, we just need to update these two variables when we backtracking


Log in to reply
 

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