题解 | 二叉树节点间的最大距离问题

#include <iostream>
#include <limits>

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 dfs(TreeNode* root, int& result) {
    if (!root) {
        return 0;
    }
    int left = dfs(root->left, result);
    int right = dfs(root->right, result);
    result = max(result, left + right + 1);
    return max(left, right) + 1;
}

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

    TreeNode* root = new TreeNode(rootVal);
    createTree(root);
    int result = 0;
    dfs(root, result);
    cout << result << endl;
    //cout << process(root)->maxDistance << endl;

    return 0;
}