二叉树的直径
# 📃 题目描述
题目链接:543. 二叉树的直径 (opens new window)
# 🔔 解题思路
和 剑指 Offer II 051. 节点之和最大的路径 - 力扣(LeetCode) (leetcode-cn.com) (opens new window) 一模一样的思路
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
// 最大直径
private int maxDistance = 0;
public int diameterOfBinaryTree(TreeNode root) {
if (root == null) {
return 0;
}
process(root);
return maxDistance;
}
// 以为 process 为起点的最大路径长度(其实就是 process 树的高度)
private int process(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = process(root.left);
int rightHeight = process(root.right);
// 注意两结点之间的路径长度是以它们之间边的数目表示,所以这里不要 + 1
maxDistance = Math.max(maxDistance, leftHeight + rightHeight);
return Math.max(leftHeight, rightHeight) + 1;
}
}
# 💥 复杂度分析
- 空间复杂度:O(LogN)
- 时间复杂度:O(N)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10