二叉树任意两个结点最长距离

秒速五厘米 2022-05-17 12:56 180阅读 0赞

给定一棵二叉树，求出树中两个结点距离的最大值。

首先明确距离最大的两个结点出现位置：1，同时在根结点的左子树中；2，同时在根结点的右子树中；3，左右子树中各有一个结点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9fY2FpX21pbmc_size_16_color_FFFFFF_t_70][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9fY2FpX21pbmc_size_16_color_FFFFFF_t_70 1][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9fY2FpX21pbmc_size_16_color_FFFFFF_t_70 2][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9fY2FpX21pbmc_size_16_color_FFFFFF_t_70 3][]

图一  第一二种情况            图二  第三种情况              图三  属于第三种情况               图四  高度等于距离

假设我们分别得到了根结点左子树中两个结点最长距离，右子树中两个结点最长距离（这是求整棵树中两个结点最长距离的子问题罢了，既然程序能够求出整棵树两个结点最长距离，那么求左右子树中的最长距离只不过是两次递归调用而已），还要得到根结点左子树高度（最低层为0），这个高度代表左子树中最底层结点到根结点距离（图四），同样可以得到右子树高度。

将左子树两个结点最长距离，有结点两个结点最长距离，左、右子树高度之和比较，取得三者中的最大值，即为这棵二叉树中两个结点距离的最大值。

\----------------------------------------------------------------------------------------------

C实现：

typedef struct Node {
        struct Node *lchild;
        struct Node *rchild;
    
        //左右子树高度（最底层结点到当前结点距离）及左右子树最大高度
        int lHeight, rHeight, height;
    }
    
    int findMaxLen(Node *root) {
        int lMaxLen, rMaxLen;
    
        if(root == NULL) return 0;
    
        lMaxLen = findMaxLen(root->lchild);
        rMaxLen = findMaxLen(root->rchild);
    
        if(root->lchild == NULL) root->lHeight = 0;
        else root->lHeight = (root->lchild->height) + 1;
    
        if(root->rchild == NULL) root->rHeight = 0;
        else root->rHeight = (root->rchild->height) + 1;
    
        //以当前结点为根结点的树的最大高度（长度）
        root->height = root->lHeight > root->rHeight ? root->lHeight : root->rHeight;
    
        return max(lMaxLen, rMaxLen, root->lHeight + root->rHeight); //max求三者最大值
    }

\---------------------------------------------------------------------------------------------

Java实现：

public int maxPathLen(TreeNode root) {
        int[] max = new int[]{Integer.MIN_VALUE};
        dfs(root, max);
        return max[0];
    }
    
    private int dfs(TreeNode root, int[] max) {
        if (root == null) return 0;
    
        int lHeight = dfs(root.left, max);
        int rHeight = dfs(root.right, max);
    
        if (lHeight + root.val + rHeight > max[0]) max[0] = lHeight + root.val + rHeight;
        if (lHeight + root.val > max[0]) max[0] = lHeight + root.val;
        if (root.val + rHeight > max[0]) max[0] = root.val + rHeight;
        if (root.val > max[0]) max[0] = root.val;
    
        return Math.max(root.val, Math.max(lHeight + root.val, root.val + rHeight));
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9fY2FpX21pbmc_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190606120529358.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9fY2FpX21pbmc=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9fY2FpX21pbmc_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190606130258859.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9fY2FpX21pbmc=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9fY2FpX21pbmc_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190606130629516.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9fY2FpX21pbmc=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9fY2FpX21pbmc_size_16_color_FFFFFF_t_70 3]: /images/20220517/e4158b8a49fc46c1b52c94ecf2caea2b.png