Looting iii[post sequence traversal and backtracking + dynamic planning]

Preface

For tree problems , There is Preface and DFS/ Medium order and balanced binary tree / Postscript and backtracking / Sequence and BFS. For home raiding , It is a classic dynamic programming problem , When a linear array is transformed into a branched tree structure , How should the state be transferred from two branches ？
Can cooperate with backtracking , Get the node savings of the two branches of the left and right children , According to actual needs , Choose to save money .

One 、 raid homes and plunder houses III

When the state transition doesn't think carefully , Encountered tree structure .

Two 、 to flash back + Dynamic programming

package everyday.tree;

public class Rob {
    
    //  Use backtracking to cooperate with dynamic programming .
    public int rob(TreeNode root) {
    
        int[] r = order(root);
        return Math.max(r[0], r[1]);
    }

    private int[] order(TreeNode root) {
    
        if (null == root) return new int[]{
    0, 0};
        int[] l = order(root.left);
        int[] r = order(root.right);
        //  Root selection , You can only choose the money saved by the deeper node .
        int first = root.val + l[0] + r[0];
        //  Don't choose the root , This is worth considering , In the left child of the root and the next layer, you can choose any one , After all, it won't be next to the root , The same goes for the right side .
        int second = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);

        return new int[]{
    second, first};
        /*  Binary tree problem ：  Preorder traversal and DFS; Middle order traversal and balanced binary tree ; Post order traversal and backtracking ; Sequence traversal and BFS; */
    }

    // Definition for a binary tree node.
    public class TreeNode {
    
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
    
        }

        TreeNode(int val) {
    
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
    
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}

summary

1） The basis of the tree problem , is , Preface and DFS/ Middle order and balanced binary / Postscript and backtracking / Sequence and BFS.
2） State transition of Dynamic Planning , It is a place worthy of careful consideration .

reference

[1] LeetCode raid homes and plunder houses