leetcode543. 二叉树的直径

leetcode543. 二叉树的直径

三月 14, 2020

leetcode543. 二叉树的直径

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

示例 :
给定二叉树

    1
   / \
  2   3
 / \     
4   5

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。

算出左右子树的路径和，把他和maxRoad相比较，大的留下来，这么不断遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxRoad=0;
    public int diameterOfBinaryTree(TreeNode root) {
         deep(root);
        return maxRoad;
    }
    public int deep(TreeNode root){
        if(root==null)return 0;
        int left=deep(root.left);
        int right=deep(root.right);
        int add=left+right;
        maxRoad=Math.max(add,maxRoad);
        return Math.max(left,right)+1;
    }
}

leetcode 41/100