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;
    }
}
全部评论

相关推荐

看到这个内容真是闹麻了。。。。。。现在有了AI以后很多人面试都会作弊吗?&nbsp;那对老老实实面试的人岂不是不公平....
程序员牛肉:公平那是对小孩子讲的童话故事,成年人的世界只有能不能接受失败的后果。 你要是能接受面试作弊被发现之后多家公司联合永久拉黑的后果,你就搞。
点赞 评论 收藏
分享
Ncsbbss:又想干活又想要工资,怎么什么好事都让你占了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务