关于算法:二叉树递归套路4最低公共祖先派对的最大快乐值

明天持续二叉树的递归套路。

给定一个二叉树的头节点，和另外两个节点 a、b，返回 a、b 的最低公共先人。

最低公共先人定义：a、b 往上找，第一个雷同的先人（这个公共先人也可能是 a 或 b 本人）

对于二叉树中的任意一个节点 X，以及两个节点 a、b，a 和 b 的最低公共先人分为两种状况。

（1）与 X 无关，即最低公共先人不是 X

a、b 在左树中某个点汇聚了

a、b 在右树中某个点汇聚了

a、b 在左树和右树中不全

（2）与 X 无关，即最低公共先人是 X

左树中找到 a、b 中的一个，右树找到另一个

X 是 a，在左树或右树中找到 b

X 是 b，在左树或右树中找到 a

也就是每次从左树和右树中咱们都须要 是否有 a，是否有 b，a 和 b 汇聚的最低先人。所以，能够定义如下的 Info 类

/**
 * @author Java 和算法学习：周一
 */
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;
    }
}

（1）首先判断为空时好不好设置，此时是好设置的，节点为空时 new Info(false, false, null)，即认为空节点不含有 a、不含有 b、最低公共先人为 null。

（2）而后依据列出的所有可能性，编写递归套路的代码，因为要整个造成递归，所以每一步都要返回 Info 类。（无脑拿到左右子树的 Info、拼凑本人的 Info、返回本人的 Info）

/**
 * @author Java 和算法学习：周一
 */
public static Info process(Node x, Node a, Node b) {if (x == null) {return new Info(false, false, null);
    }

    // 获取左右子树的信息
    Info leftInfo = process(x.left, a, b);
    Info rightInfo = process(x.right, a, b);

    // 拼凑本人的信息
    // 不要疏忽了本人是 a 或 b 的状况
    boolean findA = leftInfo.findA || rightInfo.findA || x == a;
    boolean findB = leftInfo.findB || rightInfo.findB || x == b;
    Node answer = null;
    if (leftInfo.answer != null) {
        // 左树中有答案，则此答案就是最终的答案
        answer = leftInfo.answer;
    } else if (rightInfo.answer != null) {
        // 右树中有答案，则此答案就是最终的答案
        answer = rightInfo.answer;
    } else {
        // 左树和右树都没有答案，然而找到了 a 和 b，则答案就是以后节点 X
        if (findA && findB) {answer = x;}
    }

    return new Info(findA, findB, answer);
}

（3）主函数调用递归办法获取后果

/**
 * @author Java 和算法学习：周一
 */
public static Node lowestAncestor(Node head, Node a, Node b) {if (head == null) {return null;}
    return process(head, a, b).answer;
}

所有代码地址：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/binarytree/LowestAncestor.java

员工的信息定义如下：

public static class Employee {
    // 这名员工能够带来的高兴值
    public int happy;
    // 这名员工有哪些间接上级
    List<Employee> next;
}

一个员工只有一个间接下级。也就是这个公司员工的层级构造就是一个多叉树。

当初公司邀请员工加入派对，要求不能同时邀请员工和员工的任一上级（即间接上下级不能同时邀请），如何邀请员工，能力使得加入派对的员工的高兴值是所有状况中最大的。最初返回最大的高兴值。

对于任意一个以 X 为头，含有 a、b、c 三个子节点的多叉树，最大高兴值分为两种：

（1）X 来加入派对

最大高兴值 = X.happy

+ a 不来的 max(happy)

+ b 不来的 max(happy)

+ c 不来的 max(happy)

（2）X 不来加入派对

最大高兴值 = max(a 来的 max(happy), a 不来的 max(happy) )

+ max(b 来的 max(happy), b 不来的 max(happy) )

+ max(c 来的 max(happy), c 不来的 max(happy) )

最初，最大的高兴值为以上两种状况的最大值。

也就是每次从左树和右树中咱们都须要 来，不来 的最大高兴值，所以，能够定义如下的 Info 类

/**
 * @author Java 和算法学习：周一
 */
public static class Info {
    // 来的最大收益
    public int yes;
    // 不来的最大收益
    public int no;

    public Info(int yes, int no) {
        this.yes = yes;
        this.no = no;
    }
}

（1）首先判断为空时好不好设置，此时是好设置的，节点为空时 new Info(0, 0)，即认为空节点示意来的最大收益为 0、不来的最大收益为 0。

（2）而后依据列出的所有可能性，编写递归套路的代码，因为要整个造成递归，所以每一步都要返回 Info 类。（无脑拿到所有子树的 Info、拼凑本人的 Info、返回本人的 Info）

/**
 * @author Java 和算法学习：周一
 */
public static Info process(Employee x) {if (x == null) {return new Info(0, 0);
    }

    // x 不来的最大高兴值
    int no = 0;
    // x 来的最大高兴值
    int yes = x.happy;
    for (Employee e : x.next) {Info nextInfo = process(e);
        // x 来，则所有上级都不能来
        yes += nextInfo.no;
        // x 不来，则求每个上级 来或不来 的最大值
        no += Math.max(nextInfo.yes, nextInfo.no);
    }

    return new Info(yes, no);
}

（3）主函数调用递归办法获取后果

/**
 * @author Java 和算法学习：周一
 */
public static int maxHappy(Employee head) {if (head == null) {return 0;}
    Info processInfo = process(head);
    return Math.max(processInfo.yes, processInfo.no);
}

所有代码地址：https://github.com/monday-pro/algorithm-study/blob/master/src/basic/binarytree/MaxHappy.java

关于算法:二叉树递归套路4最低公共祖先派对的最大快乐值

一、最低公共先人

1、递归套路思路

2、递归套路代码

二、派对的最大高兴值

1、递归套路思路

2、递归套路代码