Java post-order-traversal (dfs) solution, easy understand with explanation.


  • 2
    A
    public int rob(TreeNode root) {
        int[] rst = postOrderTraversal(root);
        return Math.max(rst[0],rst[1]);
    }
    
     public int[] postOrderTraversal(TreeNode node){
        int[] arr = new int[2];
        if(node==null) return arr;
        int[] left = postOrderTraversal(node.left);
        int[] right = postOrderTraversal(node.right);
        arr[0] = node.val + left[1] + right[1];
        arr[1] = Math.max(left[0],left[1]) + Math.max(right[0], right[1]);
        return arr;
    }
    

    We can tackle this problem from bottom up, for each node, we return an integer arr, arr[0] represent the maximum sum we can get if we rob this node, arr[1] represent the maximum sum we can get if we DON'T rob this node.

    arr[0] is easy to get, we just need to calculate the sum of node.val + left[1] + right[1], which represents its value, the maximum value if we do not rob its left node, and the maximum value if we do not rob its right node.

    However, for arr[1] if we don't rob the current node, we will have four choices: rob its left node or not, and rob its right node or not. Therefore, the maximum value we can get so far is to choose the respective maximum value of each child node, which is arr[1] = Math.max(left[0],left[1]) + Math.max(right[0], right[1]);

    Therefore, the maximum value of each node will be either arr[0] or arr[1], the picture shows an example. Please read it in post-order-traversal way!!

    alt text


  • 0
    Y

    The last step of calculating root node maybe is wrong in the picture. Is it?


  • 0
    A

    @YoungBella Opps, thanks for pointing out, should have been 6 + 3 = 9


Log in to reply
 

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