Java-LeetCode543. 二叉树的直径-递归&二叉树的深度

• 算法
  • 1.每个节点有三种路径：贯穿节点的路径，贯穿左子节点的路径，贯穿右子节点的路径
  • 2.贯穿节点的路径等于左子树的深度+右子树的深度，左子节点和右子节点的路径可以递归计算
  • 3.比较最大的即可

public int diameterOfBinaryTree(TreeNode root) {
    if(root == null){
        return 0;
    }

    int diameter = depth(root.left) + depth(root.right);
    int ldiameter = diameterOfBinaryTree(root.left);
    int rdiameter = diameterOfBinaryTree(root.right);
    return Math.max(diameter,Math.max(ldiameter,rdiameter));

}

private int depth(TreeNode root){
    if(root == null){
        return 0;
    }
    return 1 + Math.max(depth(root.left), depth(root.right));
}