算法提高之LeetCode刷题算法程序员

LeetCode算法题-Diameter of Binary T

2019-02-23  本文已影响117人  程序员小川

这是悦乐书的第257次更新,第270篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第124题(顺位题号是543)。给定二叉树,您需要计算树的直径长度。 二叉树的直径是树中任意两个节点之间最长路径的长度。 此路径可能会也可能不会通过根节点。例:

给出一棵二叉树

    1
   / \
  2   3
 / \
4   5

返回3,这是路径[4,2,1,3]或[5,2,1,3]的长度。

注意:两个节点之间的路径长度由它们之间的边数表示。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 解题

题目要求是求二叉树的直径,根据题目给的示例,也可以理解成从根节点开始,左子树的深度与右子树的深度之和,但是题目又说了,也可能不经过根节点,所以我们需要求两者的最大值。计算任意一个节点的最长路径值,在其中取出最大值即可。递归方法的主体,和求二叉树最大深度的代码一样,只是中间加了一步取最大值的操作而已。

此解法的时间复杂度是O(n),空间复杂度是O(n)。

public int diameterOfBinaryTree(TreeNode root) {
    helper(root);
    return max;
}

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

03 小结

算法专题目前已日更超过三个月,算法题文章124+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

上一篇下一篇

猜你喜欢

热点阅读