Leecode543. 二叉树的直径

简介: Leecode543. 二叉树的直径

题目描述:

给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

示例 :

给定二叉树

1
     / \
    2   3
   / \     
  4   5    

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

注意:两结点之间的路径长度是以它们之间边的数目表示。

解题思维:

如果根节点为空,那就直接返回0,;如果根节点不为空,那么我们可以通过递归的思想,左子树的最长路径+ 右子树的最长路径 + 1(这个加一的是根节点的一点)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return max;
    }
    private int depth(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftDepth = depth(root.left);
        int rightDepth = depth(root.right);
        max = Math.max(leftDepth + rightDepth, max);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

运行截图:


相关文章
|
6月前
leetcode-543:二叉树的直径
leetcode-543:二叉树的直径
34 0
|
存储 算法
【每日挠头算法题(9)】二叉树的直径|二叉树的层序遍历
【每日挠头算法题(9)】二叉树的直径|二叉树的层序遍历
|
6月前
|
算法 程序员
【算法训练-二叉树 三】【最大深度与直径】求二叉树的最大深度、求二叉树的直径
【算法训练-二叉树 三】【最大深度与直径】求二叉树的最大深度、求二叉树的直径
64 0
|
6月前
树形dp之没有上司的舞会
树形dp之没有上司的舞会
|
存储
【Leetcode -563.二叉树的坡度 - Nowcoder -KY11.二叉树遍历】
【Leetcode -563.二叉树的坡度 - Nowcoder -KY11.二叉树遍历】
44 0
|
6月前
|
存储 人工智能 BI
树形dp总结
树形dp总结
50 0
【Leetcode -404.左子叶之和 -543.二叉树的直径】
【Leetcode -404.左子叶之和 -543.二叉树的直径】
54 0
leetcode 543:二叉树的直径
leetcode 543:二叉树的直径
52 0
|
算法
图解LeetCode——543. 二叉树的直径
图解LeetCode——543. 二叉树的直径
10830 1
LeetCode 543. 二叉树的直径
LeetCode 543. 二叉树的直径
93 0
LeetCode 543. 二叉树的直径