二叉树节点间的最大距离

二叉树节点间的最大距离

一、题目

二叉树上的两个节点，求这两个节点之间的最大距离

二、思路

两个节点之间的距离不一定要经过一颗二叉树的根节点。我们以递归的思路来思考。既然是求二叉树的任意两个节点。那我们以二叉树的一个节点为例，这个节点组成的树；我们可以分成三种情况：

• 这个节点的左子树，求得这个节点左子树上最大的距离

• 求得这个节点右子树上最大的距离

• 这个节点左子树上离 当前节点最远的距离 + 这个节点右子树上离当前节点最远的距离 + 1

  这个 1 就是当前节点算 1 个距离。这个最远距离其实就是高度

拿到的这三个值取最大值就是以这个节点为树。这棵树上两节点之间的最大距离。

还没有完，以这个节点为树，我们知道了这个树上的两节点的最大距离还不行。这个节点也可能是其他树的子节点。我们不仅要保存这颗树上两节点之间的最大距离；还要保存这棵树上某节点到当前根节点的最大距离，这个将作为其他节点（当前节点为子节点）的一个参考数据。

然后我们分别以二叉树上的所有节点作为树，取出每颗树的最大距离，即为整棵树的两节点间的最大距离。

三、code

#include <algorithm>
#include <iostream>

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

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

class Solution {
public:
    int get_max_distance(TreeNode* root) {
        int node_distance = 0;
        return get_max_distance_internal(root, &node_distance);
    }

private:
    int get_max_distance_internal(TreeNode* root, int* node_distance) {
        if (root == nullptr) {
            *node_distance = 0;
            return 0;
        }
        int left_max = get_max_distance_internal(root->left, node_distance);
        int left_node_distance = *node_distance;
        int right_max = get_max_distance_internal(root->right, node_distance);
        int right_node_distance = *node_distance;
        *node_distance = std::max(left_node_distance, right_node_distance) + 1;
        int node_max_distance = left_node_distance + right_node_distance + 1;
        return std::max(std::max(left_max, right_max), node_max_distance);
    }
};

TreeNode* get_binary_tree() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->right->right = new TreeNode(5);
    return root;
}

int main() {
    TreeNode* root = get_binary_tree();
    Solution s;
    int res = s.get_max_distance(root);
    std::cout << "max distance: " << res << std::endl;
    return 0;
}