Leetcode-543.二叉树的直径

题目描述

运行结果

解题思路
重点就是理解题意--肯定涉及到求树的深度
注意路径可以不过根节点（也就是可以不涉及右子树）
但最长路径一定是路过根节点或者各级子树的根节点
经过某个节点的路径的节点数：为其左右子树的深度+1（左子树的深度是从根节点到最下的节点数）
在求某个子树的深度时，将经过该子树的路径长度进行更新（记录最大值）
java代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        ans=1;
        heigth(root);
        return ans-1;
    }
    //求子树的深度
    public int heigth(TreeNode root){
        if(root == null) return 0;
        int L=heigth(root.left);
        int R=heigth(root.right);
        //使ans始终记录路径的最大值
        ans=Math.max(L+R+1,ans);
        return 1+Math.max(L,R);
    }
}