Leetcode: 543. 二叉树的直径
要点:二叉树的直径就是左右子树和根节点形成的最长节点数量减一。设置一个两头变量 max,每次寻找左右子树和根节点所形成的节点数量与 max 比拟大小,较大的用 max 保留,直到最初所有左右子树和根节点形成的最长节点门路就是 max,最初用 max- 1 就是最大直径。该题的实质还是求树的深度。
class Solution {
int max = Integer.MIN_VALUE;
public int diameterOfBinaryTree(TreeNode root) {depth(root);
return max - 1;
}
public int depth(TreeNode root){if(root == null) return 0;
int l = depth(root.left);
int r = depth(root.right);
max = Math.max(max,l + r + 1);
return Math.max(l,r) + 1;
}
}