【算法题系列之十三】二叉树两叶节点的最大距离

1、题目描述
    给定一棵二叉树，计算这课二叉树的直径长度，即为二叉树任意两个节点间的最长路径。比如：

     这棵二叉树的最长路径为3。

2、解题思路
    使用递归进行求解，每次递归的过程中，先求出以某个节点为树根的二叉树的左子树的最长深度maxLeft、右子树的最长深度maxRight，并在递归函数中用一个变量maxLen来保存任意两个节点间的最长路径。在求出左子树的最长深度maxLeft和右子树的最长深度maxRight之后，就可以求出以该节点为根的二叉树的最长路径maxLen。具体代码如下：

public class Solution {

    static int maxLen = 0;

    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        TreeNode p1 = new TreeNode(1);
        TreeNode p2 = new TreeNode(2);
        TreeNode p3 = new TreeNode(3);
        TreeNode p4 = new TreeNode(4);
        TreeNode p5 = new TreeNode(5);
        TreeNode p6 = new TreeNode(6);
        TreeNode p7 = new TreeNode(7);
        TreeNode p8 = new TreeNode(8);
        root.left = p1;
        root.right = p2;
        p1.left = p3;
        p3.left = p4;
        p2.left = p5;
        p2.right = p6;
        p6.right = p7;
        p7.right = p8;
        FindMaxLen(root);
        System.out.println(maxLen);
    }

    public static void FindMaxLen(TreeNode pRoot) {
        if (pRoot == null) {
            // 空的话直接结束
            return;
        }
        if (pRoot.left == null) {
            // 左子为空，左面最大长度为0
            pRoot.maxLeft = 0;
        }
        if (pRoot.right == null) {
            // 右子为空，右面最大长度为0
            pRoot.maxRight = 0;
        }
        if (pRoot.left != null) {
            // 递归获取以左子节点为根节点的最大距离
            FindMaxLen(pRoot.left);
        }
        if (pRoot.right != null) {
            // 递归获取以右子节点为根节点的最大距离
            FindMaxLen(pRoot.right);
        }
        if (pRoot.left != null) {
            // 左面最大距离=左子左面最大距离与左子右面最大距离取最大值+1
            pRoot.maxLeft = Math.max(pRoot.left.maxLeft, pRoot.left.maxRight) + 1;
        }
        if (pRoot.right != null) {
            // 右面最大距离=右子左面最大距离与右子右面最大距离取最大值+1
            pRoot.maxRight = Math.max(pRoot.right.maxLeft, pRoot.right.maxRight) + 1;
        }
        if (pRoot.maxLeft + pRoot.maxRight > maxLen) {
            // 刷新最大距离
            maxLen = pRoot.maxLeft + pRoot.maxRight;
        }
    }

}

class TreeNode {
    TreeNode left;
    TreeNode right;
    int maxLeft;
    int maxRight;
    int data;
    public TreeNode(int data) {
        this.data = data;
    }
}

3、另一种解法：递归

public static int FindMaxLen(TreeNode pRoot) {
    if (pRoot == null) {
        return 0;
    }
    // 递归获取左子、右子的最大距离
    int maxLeft = FindMaxLen1(pRoot.left);
    int maxRight = FindMaxLen1(pRoot.right);
    // 刷新最大距离
    maxLen = Math.max(maxLeft + maxRight, maxLen);
    // 返回该节点的父节点在该侧的最大距离
    return Math.max(maxLeft, maxRight) + 1;
}