二叉树的直径
2020-10-27 本文已影响0人
小鱼嘻嘻
问题1
二叉树的最大直径
原理
- 首先,需要定义一个变量记录二叉树的直径
- 其次,递归遍历,找到每一层二叉树的
- 递归的终止条件为,当前节点为空返回0
代码
class Solution {
int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
max(root);
return max;
}
private int max(TreeNode root){
if(root==null){
return 0;
}
int left = max(root.left);
int right = max(root.right);
max = Math.max(max,left+right);
return Math.max(left,right)+1;
}
}
注意事项
- 需要使用临时遍历记录最大路径
问题2
二叉树的最大路径和
原理
- 递归找到左侧路径的最大值,找到右侧路径的最大值
- 比较当前left+right+root.val 和历史最大值的大小
- 返回当前层的最大值
代码
class Solution {
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
max(root);
return max;
}
private int max(TreeNode root){
if(root==null){
return 0;
}
int left = 0;
if(root.left!=null){
left = Math.max(left,max(root.left));
}
int right = 0;
if(root.right!=null){
right = Math.max(right,max(root.right));
}
max = Math.max(max,left+right+root.val);
return Math.max(left,right)+root.val;
}
}
注意事项
** 需要使用临时遍历记录最大路径之和