leetcode 543:二叉树的直径
543. 二叉树的直径 给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/ \
23
/ \
45
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
**注意:**两结点之间的路径长度是以它们之间边的数目表示。
【leetcode|leetcode 543(二叉树的直径)】Related Topics
树
深度优先搜索
二叉树
思路1:深度优先遍历(递归) 分析:一个节点直径长度有2种方式
- 左右子树的最大直径加1。
- 注意:我们统计左右子树的最大直径加1,但是当左右孩子为null时,需要返回-1,因为-1加1后等于0,叶子节点的直径就是0.
- 当左右孩子是叶子节点的时候,返回0,加1后就等于1.和叶子节点直径距离是1.
- 注意为空和叶子节点的返回值不同。
- 左子树的最大直径加1,再加上 右子树的最大直径加1。
class Solution {
public int diameterOfBinaryTree(TreeNode root) {
int[] result = dfs(root);
return Math.max(result[0],result[1]);
}
//result[0] 表示当前节点到叶子的最大直径
//result[1]表示这棵树中最大直径
public int[] dfs(TreeNode root){
int[] result = new int[2];
if(root == null){
result[0] = result[1] = -1;
return result;
}
if(root.left ==null && root.right == null){
return result;
}
int[] left = dfs(root.left);
int[] right = dfs(root.right);
result[0] = Math.max(left[0],right[0])+1;
result[1] = Math.max(left[0]+right[0]+2,Math.max(left[1],right[1]));
return result;
}
}解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:40.9 MB,击败了41.45% 的Java用户
改进:定义一个全局变量max,函数就不需要当前节点最大值了。
class Solution {
private int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return max;
}
public int dfs(TreeNode root){
if(root == null){
return -1;
}
if(root.left ==null && root.right == null){
return 0;
}
int left = dfs(root.left);
int right = dfs(root.right);
max = Math.max(left+right+2,max);
return Math.max(left,right)+1;
}
}
推荐阅读
- 学习记录|393. UTF-8 编码验证
- Codeforces|Fault-tolerant Network(连通块/贪心)
- 算法|K-means,K-means++方法详解-机器学习分类问题常见算法
- 算法|PyTorch中的squeeze()和unsqueeze()详解与应用案例
- 机器学习|bagging && boosting && stacking 集成学习
- 算法|Fractal解题笔记
- 动态规划|符环 解题笔记
- 557.反转字符串中的单词III(JS)——leetCode
- leetcode刷题记录|移动零——LeetCode283题