专栏首页眯眯眼猫头鹰的小树杈leetcode543. Diameter of Binary Tree

leetcode543. Diameter of Binary Tree

题目要求

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example: Given a binary tree

      1
     / \
    2   3
   / \   
  4   5    

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

二叉树的直径是指从一个叶节点到另一个叶节点的最远距离,而这个距离是指两个节点之间的路径长,注意,这条路径不一定经过根节点。

思路和代码

这里可以通过递归来完成计算,通过先递归的计算出左子树的最大高度,再递归的计算出右子树的最大高度,就可以得出当前节点可以构成的最长路径。需要将该值记录下来。再递归的返回该节点的最大高度给外层调用方运用。

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode477. Total Hamming Distance

    计算N个数字之间的汉明码距离之和。 汉明码是指两个数字的二进制表示形式中,在对应位置上值不同的数量总和。如2和4,4的二进制表达式为100, 2的二进制表达式0...

    眯眯眼的猫头鹰
  • leetcode310. Minimum Height Trees

    在无向图的生成树中,我们可以指定任何一个节点为这棵树的根节点。现在要求在这样一棵生成树中,找到生成树的高度最低的所有根节点。

    眯眯眼的猫头鹰
  • leetcode501. Find Mode in Binary Search Tree

    Given a binary search tree (BST) with duplicates, find all the mode(s) (the most...

    眯眯眼的猫头鹰
  • 高精度计算(大数相加)A + B Problem II HDU 1002(C++ and Java)

    本来以为这个题好简单的,只是输出格式有点特殊,然后,仔细一看,突然发现,貌似有点麻烦,虽然它是正整数的相加,但是,题目说,数字的长度不小于1000,事实证明,这...

    种花家的奋斗兔
  • LWC 54:699. Falling Squares

    LWC 54:699. Falling Squares 传送门:699. Falling Squares Problem: On an infinite nu...

    用户1147447
  • 保持Kubernetes容器平台稳定性

    这两天搭建了一套新的kubernetes环境,由于这套环境会被用于演示,所以持续观察了好几天这套环境,发现不少容器平台稳定性的问题,这里记录一下以备忘。

    jeremyxu
  • linux网络编程之TCP/IP基础(三):IP数据报格式和IP地址路由

    一、IP数据报格式 IP数据报格式如下: ? 注:需要注意的是网络数据包以大端字节序传输,当然头部也得是大端字节序,也就是说: The most signifi...

    s1mba
  • leetcode-278-First Bad Version(注意不要上溢)

    You are a product manager and currently leading a team to develop a new product....

    chenjx85
  • POJ-2018 Best Cow Fences(二分加DP)

    Best Cow Fences Time Limit: 1000MS Memory Limit: 30000K Total Submissio...

    ShenduCC
  • Dragoon:使用延迟测量的IP地理位置高级建模(CS)

    IP地理位置是许多应用领域的关键推动力,例如确定攻击源、定向广告和内容分发网络。尽管IP地理定位是一个持续的研究领域在一个十年中,它仍然是一个挑战性的任务,而好...

    DDDDDaemon

扫码关注云+社区

领取腾讯云代金券