程序员代码面试指南 3.20：二叉树节点间的最大距离问题

1、思路

• 树形DP套路第一步：分析答案来自哪些可能性：

  1、以root为头节点的子树，最大距离可能是左子树上的最大距离；

  2、以root为头节点的子树，最大距离可能是右子树上的最大距离；

  3、以root为头节点的子树，最大距离可能是左子树上高度 + 右子树高度 + 1（root节点本身）；

• 第二步：根据第一步的分析列出所有需要的信息，左子树和右子树需要知道自己这棵子树上的最大距离 maxDistance 以及高度 height这两个信息；

• 第三步：根据第二步的信息汇总，用一个新的结构体 ReturnType来存储上述两个信息；

• 第四步：设计递归函数，整合信息。

2、代码

#include <iostream>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left, *right;

    TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {}
};

struct ReturnType                                           //新结构体
{
    int maxDistance;
    int height;

    ReturnType(int _maxDistance, int _height) : maxDistance(_maxDistance), height(_height) {}
};

void createTree(TreeNode *root)                             //建树
{
    int rootVal, leftVal, rightVal;
    cin >> rootVal >> leftVal >> rightVal;

    if (leftVal != 0)
    {
        root->left = new TreeNode(leftVal);
        createTree(root->left);
    }

    if (rightVal != 0)
    {
        root->right = new TreeNode(rightVal);
        createTree(root->right);
    }
}

ReturnType* process(TreeNode* root)
{
    if (root == nullptr) return new ReturnType(0, 0);

    ReturnType *leftData = process(root->left);
    ReturnType *rightData = process(root->right);

    //更新最大高度以及最大距离信息
    int _height = max(leftData->height, rightData->height) + 1;
    int _maxDistance = max(leftData->height + rightData->height + 1, 
    max(leftData->maxDistance, rightData->maxDistance));

    return new ReturnType(_maxDistance, _height);
}

int main()
{
    int n, rootVal;
    cin >> n >> rootVal;

    TreeNode *root = new TreeNode(rootVal);
    createTree(root);

    cout << process(root)->maxDistance << endl;

    return 0;
}