LeetCode543.二叉树的直径(任意两结点最长距离)

LeetCode ：https://leetcode-cn.com/problems/diameter-of-binary-tree/

题目描述：

给定一棵二叉树，你需要计算它的直径长度。

一棵二叉树的直径长度是任意两个结点路径长度中的最大值。

提示：这条路径可能穿过也可能不穿过根结点。

示例：给定二叉树

1
/ \
2 3
/ \
4 5

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]

注意：两结点之间的路径长度是以它们之间边的数目表示。

解题思路：

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

首先明确距离最大的两个结点出现位置：

1）同时在根结点的左子树中（图一）

2）同时在根结点的右子树中（图三）

3）左右子树中各有一个结点（图二）

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

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

解法1：从根节点，依次递归遍历左右节点（二叉树层次太深，有可能栈溢出）

使用递归进行求解，每次递归的过程中：

1）先求出以某个节点为树根的二叉树的左子树的最长深度 leftHigh、右子树的最长深度rightHigh

2）然后在递归函数中，用一个变量max来保存任意两个节点间的最长路径。

3）在求出左子树的最长深度 leftHigh 和右子树的最长深度 rightHigh 之后，就可以求出以该节点为根的二叉树的最长路径max。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int max = 0;    // 全局变量, 保存最长边数
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null) return 0;  // 根节点为空

        // 另起二叉树递归函数, 不能在本函数递归, 因为无法返回最大值max
        binaryTreeMaxHight(root);
        return max;
    }

    private int binaryTreeMaxHight(TreeNode root) {
        // 2. 左右子节点的递归返回条件
        if(root == null) return 0;

        // 1. 遍历左右子节点, 并求边数
        int leftHight = binaryTreeMaxHight(root.left);
        int rightHigh = binaryTreeMaxHight(root.right);

        // 3. 更新根节点边数的最大值
        if(leftHight + rightHigh > max) {
            max = leftHight + rightHigh;
        }

        // 4. 左右叶节点加1, 计算叶节点的边数
        return Math.max(leftHight, rightHigh) + 1;  
    }
}

参考推荐：

八大排序算法图文讲解

LeetCode 622. 设计循环队列

LeetCode 19. 删除链表的倒数第 N 个结点

LeetCode 543. 二叉树的直径 (任意两结点最长距离)