543. 二叉树的直径

543. 二叉树的直径

思路：直径一定是「叶子 <---> 叶子」，所以我们可以递归求经过每个结点（分隔左右子树）的直径，注意前置条件是先获取左右子树的高度。
时间：O(n)，空间：O(n)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int maxDiameter = 0;

    public int dp(TreeNode root) {
        if(root == null) return 0;
        int leftH = dp(root.left);
        int rightH = dp(root.right);
        // 容易出错的地方！！！
        if(root.left != null) leftH += 1;
        if(root.right != null) rightH += 1;

        maxDiameter = Math.max(maxDiameter, leftH+rightH);
        return Math.max(leftH, rightH);
    }

    public int diameterOfBinaryTree(TreeNode root) {
        dp(root);

        return maxDiameter;
    }
}