求二叉树节点的最大距离（最大直径）

题目：写一个程序求一棵二叉树中相距最远的两个节点之间的距离。

力扣：543. 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

第一种实现方法（常规）

计算一个二叉树的最大距离有两个情况:

1. 路径经过根节点：路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。
2. 路径不经过根节点：而是左子树或右子树的最大距离路径，取其大者。

所以，需要计算这两个情况的路径距离，并取其大者，就是该二叉树的最大距离。

    class Node {
        public Node left; //左子树
        public Node right; //右子树
        public int lMax; //左子树的最大距离
        public int rMax; //右子树的最大距离
        public int val; //节点的值
    }

    int maxPath = 0;

    /**
     * 求二叉树中节点的最大距离
     * @param root
     */
    public void findMaxPath(Node root){
        if (root == null){
            return;
        }
        // 如果左子树为空，那么该节点的左边最长距离为0
        if (root.left == null){
            root.lMax = 0;
        }
        if (root.right == null){
            root.rMax = 0;
        }
        // 如果左子树不为空，递归寻找左子树最长距离
        if (root.left != null){
            findMaxPath(root.left);
        }
        if (root.right != null){
            findMaxPath(root.right);
        }
        // 计算左子树最长节点距离
        if (root.left != null){
            int len = 0;
            if (root.left.lMax > root.left.rMax){
                len = root.left.lMax;
            }else{
                len = root.left.rMax;
            }
            root.lMax = len + 1;
        }
        if (root.right != null){
            int len = 0;
            if (root.right.lMax > root.left.rMax){
                len = root.right.lMax;
            }else{
                len = root.right.rMax;
            }
            root.rMax = len + 1;
        }
        // 更新最长距离
        if (root.lMax + root.rMax > maxPath){
            maxPath = root.lMax + root.rMax;
        }
    }

第二种实现方法（简单解法）

第一种方案比较复杂，代码也比较多。

我们可以换一种思路：此题中，最终是求2个节点间的路径。虽然这个路径可能不经过根节点，但是，必然会以一个节点为根（根节点或子树根节点），2个目标节点分布在这个根节点的左子树和右子树中。所以，等同于“计算每个节点的左子树和右子树的高度和，然后取最大值”。

可以将二叉树的直径转换为：二叉树的每个节点的左右子树的高度和的最大值。

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
    
    
    int maxPath = 0;
      /**
     * 求二叉树中节点的最大距离
     * @param root
     */
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return maxPath;
    }
    public int depth(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = depth(root.left);
        int right = depth(root.right);
        
        if(left + right> maxPath){
            maxPath = left + right;
        }
        return Math.max(left, right) + 1;
    }