LeetCode-543-二叉树的直径

LeetCode-543-二叉树的直径

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

示例1:

给定二叉树

1
2
3
4
5
    1
/ \
2 3
/ \
4 5

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

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

解题思路

方法1、DFS:

  1. 二叉树的直径是不一定经过root节点的,可能存在于每个子树中,所以需要遍历每个节点的左右子树深度。动态记录最大的直径
  2. 直径 = max(左子树深度+右子树深度)
  3. 某节点子树的深度 = max(某节点左子树深度,某节点右子树深度)+1

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int res = 0;
public int diameterOfBinaryTree(TreeNode root) {
if(root==null) return 0;
calDepth(root);
return res;
}

public int calDepth(TreeNode root){
if(root==null) return 0;
int left = calDepth(root.left);
int right = calDepth(root.right);
res = Math.max(left+right,res);
return Math.max(left,right)+1;
}
}
打赏了解一下?
0%