【数据结构】-求二叉树中节点的最大距离

vlambda
2021-07-07

【数据结构】-求二叉树中节点的最大距离

问题：求二叉树中节点的最大距离

如果把树看做是一个图，它必然是连通的，任一节点总有路径到其他任何节点，这个题目就是求这样最长的一条路径。距离最大的两个节点可能是一个在左子树，一个在右子树，也可能是在一个子树上。下面的图展示了这两种情况。

【数据结构】-求二叉树中节点的最大距离

把这个问题转化一下：树中的每一个节点都是一颗子树的根，对于这棵子树而言，它左子树的高度是MaxLeft，右子树的高度是MaxRight，求所有子树中(MaxLeft + MaxRight)的最大值是多少？

在图上标出了每个节点左子树的长度和右子树的长度，叶子节点的左右子树长度都是0。每个节点左子树的长度是左孩子的左子树长度和左孩子右子树长度中较长的那个再加1,，这句话比较绕，但是好理解，比如A->MaxLeft = FindMaxLen(B->MaxLeft,B->MaxRight) + 1，这样很明了了吧。有了上面的信息之后，我们可以计算每棵子树的(MaxLeft + MaxRight)，其中最大者就是结果。由于树的定义是递归的，所以用递归的方式更容易编程。

算法步骤：

（1）初始化二叉树，并将每个节点MaxLeft和MaxRight初始化为0，定义二叉树中节点的最大距离MaxLen = 0

（2）为了计算一个节点的MaxLeft和MaxRight，需要采用后序遍历策略，递归的计算出它左孩子pLeft的MaxLeft,MaxRight，MaxLeft = FindMaxLen(pLeft->MaxLeft + pLeft->MaxRight) + 1；和右孩子pRight的MaxLeft,MaxRight，MaxRight = FindMaxLen(pRight->MaxLeft,pRight->MaxRight) + 1；

（3）对于每一个节点，计算MaxLeft + MaxRight，如果其值大于MaxLen，则MaxLen = MaxLeft + MaxRight，最后MaxLen就是最大距离。

代码如下：

public class MaxDistance {
    static int  MaxLen=0;

    public void FindMaxLen(Node pRoot){
        if(pRoot==null){
            return;
        }
        if(pRoot.pLeft==null){
            pRoot.MaxLeft=0;
        }
        if(pRoot.pRight==null){
            pRoot.MaxRight=0;
        }
        if(pRoot.pLeft!=null){
            FindMaxLen(pRoot.pLeft);
        }
        if(pRoot.pRight!=null){
            FindMaxLen(pRoot.pRight);
        }
        if(pRoot.pLeft!=null){
            int nTempMax=0;
            nTempMax=pRoot.pLeft.MaxLeft>pRoot.pLeft.MaxRight?pRoot.pLeft.MaxLeft:pRoot.pLeft.MaxRight;
            pRoot.MaxLeft=nTempMax+1;
        }
        if(pRoot.pRight!=null){
            int nTempMax=0;
            nTempMax=pRoot.pRight.MaxLeft>pRoot.pRight.MaxRight?pRoot.pRight.MaxLeft:pRoot.pRight.MaxRight;
            pRoot.MaxRight=nTempMax+1;
        }
        if(pRoot.MaxLeft+pRoot.MaxRight>MaxLen){
            MaxLen=pRoot.MaxLeft+pRoot.MaxRight;
        }
    }
    public static void main(String[] args) {
        Node root=new Node(0);
        Node p1=new Node(1);
        Node p2=new Node(2);
        Node p3=new Node(3);
        Node p4=new Node(4);
        Node p5=new Node(5);
        Node p6=new Node(6);
        Node p7=new Node(7);
        Node p8=new Node(8);
        root.pLeft=p1;
        root.pRight=p2;
        p1.pLeft=p3;
        p3.pLeft=p4;
        p2.pLeft=p5;
        p2.pRight=p6;
        p6.pRight=p7;
        p7.pRight=p8;
        System.out.println(MaxLen);
        new MaxDistance().FindMaxLen(root);
        System.out.println(MaxLen);
    }
}
class Node{
    Node pLeft;
    Node pRight;
    int MaxLeft;
    int MaxRight;
    int data;
    public Node(int data){
        this.data=data;
    }
}