leetcode543.二叉树的直径

当前顶点作为拐点时，求左子树加上右子树的高度可以求出该通过该顶点的直径大小，再对该顶点和左右子节点作为拐点时直径大小进行比对，返回最大值

缺点是递归了多次

/*** 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 {private int dfs(TreeNode root) {if (root == null) {return 0;} else {return 1 + Math.max(dfs(root.left), dfs(root.right));}}public int diameterOfBinaryTree(TreeNode root) {if(root==null)return 0;int leftHeight = dfs(root.left);int rightHeigh = dfs(root.right);return Math.max(leftHeight+rightHeigh,Math.max(diameterOfBinaryTree(root.left),diameterOfBinaryTree(root.right)));}
}