【C++二叉树节点间的最大距离问题】

要点：

学习树形dp套路：分析可能性–>左子树、右子树、整棵树的角度考虑
用递归先要左树信息和右数信息，然后再根据这些信息更新当前结点的信息

---

TIPS：

1.一定要注意递归时辅助变量的更新问题，此处qu不带引用会使初始化二叉树出错。
2.当前最大距离等于左树最大距离、右树最大距离、左右树高度和加一

---

代码：

参靠左神代码编写

#include <iostream>
#include <queue>
using namespace std;

struct Node //二叉树结点
{
    int value;
    Node *left;
    Node *right;
    Node() : value(0), left(nullptr), right(nullptr) {}
    Node(int a) : value(a), left(nullptr), right(nullptr) {}
    Node(int a, Node *left, Node *right) : value(a), left(left), right(right) {}
};

struct ReturnType //自定义返回类型(返回子树最大距离和树高)
{
    int maxlen; //最大距离
    int height; //树高
    ReturnType() : maxlen(0), height(0) {}
    ReturnType(int a, int b) : maxlen(a), height(b) {}
};

ReturnType process(Node *head)
{
    if (head == nullptr)
    {
        return ReturnType(0, 0);
    }
    ReturnType left_ret = process(head->left);                   //向左数要信息
    ReturnType right_ret = process(head->right);                 //向右数要信息
    int pre_height = max(left_ret.height, right_ret.height) + 1; //计算当前结点信息
    int pre_maxlen = max(max(left_ret.maxlen, right_ret.maxlen), left_ret.height + right_ret.height + 1);
    return ReturnType(pre_maxlen, pre_height);
}

//先序遍历创建二叉树
Node *Initial_Tree(queue<int> &qu) // qu一定要带引用！！！！！！！！
{
    int data = qu.front();
    qu.pop();
    if (data == -1)
    {
        return nullptr;
    }
    Node *head = new Node(data);
    head->left = Initial_Tree(qu);
    head->right = Initial_Tree(qu);
    return head;
}

/* 先序遍历
void show(Node *head)
{
    if (head == nullptr)
    {
        return;
    }
    cout << head->value << " ";
    show(head->left);
    show(head->right);
}
*/

int main()
{
    /*                  1
                    /       \
                   2         3
                  /         /  \
                 4         5    6
                  \       /
                   7     8
    */
    int arr[] = {1, 2, 4, -1, 7, -1, -1, -1, 3, 5, 8, -1, -1, -1, 6, -1, -1};
    queue<int> qu;
    for (int a : arr)
    {
        qu.push(a);
    }
    Node *head = Initial_Tree(qu);
    ReturnType ret = process(head);
    cout << "最大距离为:" << ret.maxlen << endl;
    // show(head);
    return 0;
}

类似题目：
员工和老板不能一起参加party，每个人有一个快乐值，求怎么安排人员有最大快乐值

最大快乐值代码：

#include <iostream>
#include <list>
using namespace std;

struct Employee
{
    int happy;
    list<Employee> subpeo;
    Employee() : happy(0) {}
    Employee(int a) : happy(a) {}
    Employee(int a, list<Employee> b) : happy(a), subpeo(b) {}
};

struct ReturnData //返回类型
{
    int qu_max;
    int bu_max;
    ReturnData() {}
    ReturnData(int a, int b) : qu_max(a), bu_max(b) {}
};

ReturnData procrss(Employee x)
{
    if (x.subpeo.empty())
    {
        return ReturnData(x.happy, 0);
    }
    int qu = x.happy;              // x去
    int bu = 0;                    // x不去
    for (Employee empl : x.subpeo) //遍历每个子结点
    {
        ReturnData sub_data = procrss(empl);         //取每个子节点的信息
        qu += sub_data.bu_max;                       //更新当前结点的信息(x去时的最大值 : 所有子结点不去的最大值的和)
        bu += max(sub_data.qu_max, sub_data.qu_max); // x不去时的最大值: 所有子节点去和不去时的最大值的和
    }
    return ReturnData(qu, bu);
}

int main()
{
    /*                            A(4)
                        /          |         \
                      B(2)        I(30)      C(6)
                /     |     \                /  \
              D(4)  E(7)   F(10)           G(5)  H(2)         */

    //初始化tree
    Employee D(4);
    Employee E(7);
    Employee F(10);
    Employee G(5);
    Employee H(2);
    Employee I(30);
    list<Employee> B_sub = {D, E, F};
    Employee B(2, B_sub);
    list<Employee> C_sub = {G, H};
    Employee C(6, C_sub);
    list<Employee> A_sub = {B, C, I};
    Employee A(4, A_sub);

    ReturnData dat = procrss(A);
    int result = max(dat.bu_max, dat.qu_max);
    cout << "最大快乐值为:" << result << endl;
    return 0;
}