Today, continue the recursive routine of binary tree.
1, Lowest common ancestor
Given the head node of a binary tree and the other two nodes a and b, return the lowest common ancestor of a and b.
Definition of lowest common ancestor: A and b look up and find the first same ancestor (this common ancestor may also be a or b itself)
1. Recursive routine idea
For any node X in the binary tree and the lowest common ancestor of two nodes a, b, a and b, there are two cases.
(1) It has nothing to do with X, that is, the lowest common ancestor is not X
a. b converges at a point in the left tree
a. b converges at a point in the right tree
a. b incomplete in left and right trees
(2) Related to x, that is, the lowest common ancestor is X
Find one of a and b in the left tree and the other in the right tree
X is a, find b in the left or right tree
X is b, find a in the left or right tree
That is, every time from the left tree and the right tree, we need whether there is a, whether there is the lowest ancestor of b, a and b. Therefore, the following Info classes can be defined
/**
* @author Java And algorithm learning: Monday
*/
public static class Info{
public boolean findA;
public boolean findB;
public Node answer;
public Info(boolean findA, boolean findB, Node answer) {
this.findA = findA;
this.findB = findB;
this.answer = answer;
}
}
2. Recursive routine code
(1) First, judge whether it is good to set when the node is empty. When the node is empty, new Info(false, false, null), that is, it is considered that the empty node does not contain a, b and the lowest common ancestor is null.
(2) Then write the code of the recursive routine according to all the possibilities listed. Because the whole recursion is to be formed, the Info class must be returned at each step. (no brain gets the Info of the left and right subtrees, pieces together his own Info, and returns his own Info)
/**
* @author Java And algorithm learning: Monday
*/
public static Info process(Node x, Node a, Node b) {
if (x == null) {
return new Info(false, false, null);
}
//Get the information of left and right subtrees
Info leftInfo = process(x.left, a, b);
Info rightInfo = process(x.right, a, b);
//Piece together your own information
//Don't overlook the fact that you are a or b
boolean findA = leftInfo.findA || rightInfo.findA || x == a;
boolean findB = leftInfo.findB || rightInfo.findB || x == b;
Node answer = null;
if (leftInfo.answer != null) {
//If there is an answer in the left tree, this answer is the final answer
answer = leftInfo.answer;
} else if (rightInfo.answer != null) {
//If there is an answer in the right tree, this answer is the final answer
answer = rightInfo.answer;
} else {
//Neither the left tree nor the right tree has an answer, but if a and b are found, the answer is the current node X
if (findA && findB) {
answer = x;
}
}
return new Info(findA, findB, answer);
}
(3) The main function calls the recursive method to get the result
/**
* @author Java And algorithm learning: Monday
*/
public static Node lowestAncestor(Node head, Node a, Node b) {
if (head == null) {
return null;
}
return process(head, a, b).answer;
}
2, Maximum party happiness
Employee information is defined as follows:
public static class Employee {
//The happiness that this employee can bring
public int happy;
//What are the direct subordinates of this employee
List<Employee> next;
}
An employee has only one direct superior. That is, the hierarchical structure of the company's employees is a multi tree.
At present, when the company invites employees to a party, it is required that employees and any subordinate of employees cannot be invited at the same time (that is, direct superiors and subordinates cannot be invited at the same time). How to invite employees so that the happiness value of employees participating in the party is the largest in all cases. Finally, return the maximum happiness value.
1. Recursive routine idea
For any multi fork tree with X as the head and containing three child nodes a, b and c, the maximum happiness value is divided into two types:
(1) X came to the party
Maximum happiness = X.happy
+ a max(happy)
+ b max(happy)
+ c max(happy)
(2) X won't come to the party
Maximum happiness = max (max(happy) from a, max(happy) from a)
+ max (max(happy) from B, max(happy) from b)
+ max (max(happy) from C, max(happy) from C)
Finally, the maximum happiness value is the maximum value of the above two cases.
That is, we need the maximum happiness value from the left tree and the right tree every time. Therefore, we can define the following Info class
/**
* @author Java And algorithm learning: Monday
*/
public static class Info {
//Maximum benefit from
public int yes;
//Maximum benefit of not coming
public int no;
public Info(int yes, int no) {
this.yes = yes;
this.no = no;
}
}
2. Recursive routine code
(1) First, judge whether it is good to set the empty node. At this time, it is good to set. When the node is empty, new Info(0, 0), that is, it is considered that the maximum benefit represented by the empty node is 0 and the maximum benefit not coming is 0.
(2) Then write the code of the recursive routine according to all the possibilities listed. Because the whole recursion is to be formed, the Info class must be returned at each step. (wunao gets the Info of all subtrees, pieces together his own Info, and returns his own Info)
/**
* @author Java And algorithm learning: Monday
*/
public static Info process(Employee x) {
if (x == null) {
return new Info(0, 0);
}
//Maximum happiness of x not coming
int no = 0;
//Maximum happiness from x
int yes = x.happy;
for (Employee e : x.next) {
Info nextInfo = process(e);
//If x comes, all subordinates cannot come
yes += nextInfo.no;
//If x does not come, find the maximum value of ， coming or not coming ， for each subordinate
no += Math.max(nextInfo.yes, nextInfo.no);
}
return new Info(yes, no);
}
(3) The main function calls the recursive method to get the result
/**
* @author Java And algorithm learning: Monday
*/
public static int maxHappy(Employee head) {
if (head == null) {
return 0;
}
Info processInfo = process(head);
return Math.max(processInfo.yes, processInfo.no);
}