543. 二叉树的直径

题目

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

分析

思路和算树最大高度的那题类似，最大值一定是在二叉树的左右子树高度的和，每次递归将左右子树长度相加与最大值比较并记录，返回左右子树中最大的，时间复杂度为O（n），空间复杂度为O（lgn）.

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //每次递归将左右子树长度相加与最大值比较并记录，返回左右子树中最大的
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        f(root);
        return max;
    }
    int f(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = f(root.left);
        int right = f(root.right);
        max = Math.max(max,left+right);
        return Math.max(left,right)+1;
    }
}