计算二叉树中任意两个节点的距离

1.问题描述

二叉树中任意两个节点的距离指的从一个节点到达另一个节点所需要的最小边数。

2.问题求解

假设root是二叉树的根节点；n1和n2是给定二叉树的两个节点的数值。
lca是n1和n2的最小公共祖先；Dist（n1, n2）为n1和n2之间的距离。

因此，两节点距离的计算公式为：

Dist(n1, n2) = Dist(root, n1) + Dist(root, n2) - 2*Dist(root, lca) 

代码如下：

#include<iostream>
using namespace std;

typedef int KeyType;
typedef struct BinaryTreeNode
{
    KeyType key;
    struct BinaryTreeNode *left;
    struct BinaryTreeNode *right;
}BTNode, *BiTree;
//创建二叉树节点
BTNode *CreateBTNode(KeyType key)
{
    BTNode *node = new BTNode;
    node->key = key;
    node->left = node->right = NULL;
    return node;
}
//对于给定的树中两节点n1和n2,返回两者lca的指针
BTNode *findLCA(BTNode *root, KeyType n1, KeyType n2)
{
    if(root == NULL) return NULL;

    //(1)n1,n2中的一个是另一个的父节点，即为LCA
    if(root->key==n1 || root->key==n2)
        return root;
    //(2)n1,n2没有父子关系，这时又存在两种情况：
    //case1：同在一个子树。case2：分别在两个子树。
    BTNode *left_lca=findLCA(root->left, n1, n2);
    BTNode *right_lca=findLCA(root->right, n1, n2);
    //都为真,说明两边子树都能找到n1或n2,这是case2的情况
    if(left_lca && right_lca)
        return root;//当n1,n2分别在两个子树时lca即为根节点
    //case1的情况
    return (left_lca != NULL)?left_lca:right_lca;
}

//返回key节点在root中的第几层，-1表示没有在root子树下找到
int findLevel(BTNode *root, KeyType key, int level)
{
    if(root==NULL)
        return -1;
    if(root->key==key)
        return level;
    //递归查找左子树
    int lev=findLevel(root->left, key, level+1);
    if(lev==-1)//左子树没有找到则到右子树查找
        return findLevel(root->right, key, level+1);
    else
        return lev;
}
//利用公式Dist(n1, n2)=Dist(root, n1)+Dist(root, n2)-2*Dist(root, lca)
int NodesDistance(BTNode *root, KeyType n1, KeyType n2)
{
    BTNode *lca = findLCA(root, n1, n2);
    int dis_lca = findLevel(root, lca->key, 0);
    int dis_n1 = findLevel(root, n1, 0);
    int dis_n2 = findLevel(root, n2, 0);
    //计算n1和n2的距离
    int dis_n1_n2 = dis_n1 + dis_n2 - 2*dis_lca;
    return dis_n1_n2;
}
int main()
{
    BTNode *root = CreateBTNode(1);
    root->left = CreateBTNode(2);
    root->right = CreateBTNode(3);
    root->left->left = CreateBTNode(4);
    root->left->right = CreateBTNode(5);
    root->right->left = CreateBTNode(6);
    root->right->right = CreateBTNode(7);
    root->right->left->right = CreateBTNode(8);
    cout <<"Distance(4, 5): "<<NodesDistance(root, 4, 5)<<endl;
    cout <<"Distance(4, 6): "<<NodesDistance(root, 4, 6)<<endl;
    cout <<"Distance(3, 4): "<<NodesDistance(root, 3, 4)<<endl;
    cout <<"Distance(2, 4): "<<NodesDistance(root, 2, 4)<<endl;
    cout <<"Distance(8, 5): "<<NodesDistance(root, 8, 5)<<endl;
    return 0;
}

转自：https://blog.csdn.net/will130/article/details/49536847