Tree DP routines

The first step of the tree DP routine:

In a subtree starting with a node X, the possibilities of the answer are analyzed in terms of the left subtree of X, the right subtree of X, and the entire tree of X

Note: first, only the most node analysis can be done, so that the analysis will not be chaotic, do not think about the following node will be what

Step 2 of tree DP routine:

Make a list of all the information you need based on the possibility analysis in step 1

Step 3 of tree DP routine:

Combine the information from step 2, make the same request for the left and right trees, and write out the information structure

Step 4 of tree DP routine:

Design a recursive function that deals with the answer to a node that starts with X. The four small steps include designing the recursive basecase, getting all the information from the left and right trees directly by default, and integrating the possibilities and returning the information structure of the third step

Supplementary topic 1

The maximum distance between nodes in a fork tree

Starting from node A of the binary tree, you can go up or down, but the nodes along the path can only pass through once. The number of nodes on the path when you reach node B is called the distance from A to B. Then there is a distance between any two nodes of the binary tree.

Correlation analysis

The relevant code

Public static class Node{public int value; public Node left; public Node right; public Node(int data){ this.value = data; Public static class ReturnType{public int maxDistance; public static class ReturnType{public int maxDistance; public int h; public ReturnType(int m, int h){ this.maxDistance = m; this.h = h; } } public static int maxDistance(Node head){ int[] record = new int[1]; // return posOrder(head, record); return process(head).maxDistance; } public static int posOrder(Node head, int[] record) {if (head == null){record[0] = 0; return 0; } // return the left maximum value int lmax = posOrder(head.left, record); Int maxfromLeft = record[0]; Int rmax = posOrder(head.right, record); Int maxFromRight = record[0]; Int curNodeMax = maxfromLeft + maxFromRight + 1; Record [0] = math. Max (maxfromLeft, maxFromRight) + 1; return Math.max(Math.max(lmax, rmax), curNodeMax); } public static ReturnType process(Node head){if (head == null){return new ReturnType(0,0); } ReturnType leftReturnType = process(head.left); ReturnType rightReturnType = process(head.right); int includeHeadDistance = leftReturnType.h + 1 + rightReturnType.h; int p1 = leftReturnType.maxDistance; int p2 = rightReturnType.maxDistance; int resultDistance = Math.max(Math.max(p1, p2), includeHeadDistance); return new ReturnType(resultDistance,Math.max(leftReturnType.h, rightReturnType.h) + 1); } public static void main(String[] args){ Node head1 = new Node(1); head1.left = new Node(2); head1.right = new Node(3); head1.left.left = new Node(4); head1.left.right = new Node(5); head1.right.left = new Node(6); head1.right.right = new Node(7); head1.left.left.left = new Node(8); head1.right.left.right = new Node(9); System.out.println(maxDistance(head1)); }Copy the code

Supplementary topic 2

Maximum happiness of the party

Correlation analysis

The relevant code

Public static class Employee{public int happy; Public List<Employee> nexts; } // Define the return value structure, because it is separated by the header, it is concluded that it is necessary to return the maximum value of the node, Public static class ReturnType{public int laiMaxHappy; public int buMaxHappy; public ReturnType(int lai, int bu){ this.laiMaxHappy = lai; this.buMaxHappy = bu; Public static int maxHappy(Employee boss){ReturnType headReturnType = process(boss); return Math.max(headReturnType.laiMaxHappy, headReturnType.buMaxHappy); } public static ReturnType process(Employee x){if (x.nexts.isempty ()){// return new when x is a basic Employee ReturnType(x.happy,0); } int lai = x.happy; int bu = 0; for (Employee next : x.nexts){ ReturnType nextReturnType = process(next); / / when x to my bottom employees not only to lai + = nextReturnType. BuMaxHappy; / / when x didn't come, I am the bottom of the employees can choose to, also can choose not to, took the biggest bu + = math.h Max (nextReturnType. LaiMaxHappy, nextReturnType. BuMaxHappy); } return new ReturnType(lai, bu); }Copy the code