题解 | #二叉树的直径#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    
    public class Info {
        public int depth;
        public int path;
        public Info (int depth, int path) {
            this.depth = depth;
            this.path = path;
        }
    }
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int diameterOfBinaryTree (TreeNode root) {
        // write code here
        
        // 一些特殊情况的处理
        if (null == root) {
            return 0;
        }
        if (null == root.left && null == root.right) {
            return 1;
        }
        // 具体代码的实现
        // 调用递归函数
        return process(root).path - 1;
    }
    
    public Info process(TreeNode node) {
        if (null == node) {
            return new Info(0, 0);
        }
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        int curDepth = Math.max(leftInfo.depth, rightInfo.depth) + 1;
        int maxPath = Math.max(leftInfo.depth + rightInfo.depth + 1, Math.max(leftInfo.path, rightInfo.path));
        return new Info(curDepth, maxPath);
    }
}