2.3 二叉树中的最大路径和
题目描述：路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给定一个二叉树的根节点 root ，返回其 最大路径和，即所有路径上节点值之和的最大值。
思路：
1.最大路径和的可能性：
- p1: 和x头节点无关，左树的最大路径和 就是最大路径和
- p2: 和x头节点无关，右树的最大路径和 就是最大路径和
- p3: 和x有关，左树的单边最大路径和 + 右树的单边最大路径和 + x.val
- p4: 和x有关，左树的单边最大路径和 + x.val（因为节点可能是负数所以存在这种可能）
- 和x有关，右树的单边最大路径和 + x.val（因为节点可能是负数所以存在这种可能）
- 和x有关，x.val（因为节点可能是负数所以存在这种可能）
2.需要收集的信息：
- 以任何节点作为root时的整棵树最大路径和：maxPathVal
- 以任何节点作为root时的整棵树的单边最大路径和：maxSinglePathVal
3.逻辑
- 空节点返回null，不能设置为0，因为路径和相加也有可能为0，需要区别
- maxSinglePathVal = Math.max(x.val ,Math.max(左树.maxSinglePathVal, 右树.maxSinglePathVal));
- maxPathVal = Math.max(p1,p2,p3,p4,p5,p6)
public static int maxPathVal(TreeNode node){
if(node == null){
return 0;
}
if(node.left==null && node.right == null){
return node.val;
}
return process(node).maxPathVal;
}
public static PathValInfo process(TreeNode treeNode){
//初始值不能设置为0，可能会和0混淆
if(treeNode == null){
return null;
}
//1.收集信息
PathValInfo leftInfo = process(treeNode.left);
PathValInfo rightInfo = process(treeNode.right);
//分情况讨论
if(leftInfo == null && rightInfo == null){
return new PathValInfo(treeNode.val, treeNode.val);
}
if(leftInfo != null && rightInfo != null){
int maxSinglePathVal = Math.max(treeNode.val, treeNode.val + Math.max(leftInfo.maxSinglePathVal, rightInfo.maxSinglePathVal));
int p1 = leftInfo.maxPathVal;
int p2 = rightInfo.maxPathVal;
int p3 = leftInfo.maxSinglePathVal + rightInfo.maxSinglePathVal + treeNode.val;
//考虑负数的情况
int p4 = leftInfo.maxSinglePathVal + treeNode.val;
int p5 = rightInfo.maxSinglePathVal + treeNode.val;
int p6 = treeNode.val;
int maxPathVal = Math.max(p1, Math.max(p2, Math.max(p3, Math.max(p4, Math.max(p5,p6)))));
return new PathValInfo(maxPathVal, maxSinglePathVal);
}
//右树不为空
if(leftInfo == null){
int maxSinglePathVal = Math.max(treeNode.val + rightInfo.maxSinglePathVal, treeNode.val);
int p2 = rightInfo.maxPathVal;
int p5 = rightInfo.maxSinglePathVal + treeNode.val;
int p6 = treeNode.val;
int maxPathVal = Math.max(p2, Math.max(p5, p6));
return new PathValInfo(maxPathVal, maxSinglePathVal);
}
//左树不为空
int maxSinglePathVal = Math.max(treeNode.val + leftInfo.maxSinglePathVal, treeNode.val);
int p1 = leftInfo.maxPathVal;
int p4 = leftInfo.maxSinglePathVal + treeNode.val;
int p6 = treeNode.val;
int maxPathVal = Math.max(p1, Math.max(p4, p6));
return new PathValInfo(maxPathVal, maxSinglePathVal);
}
public static class PathValInfo{
public Integer maxPathVal;
public Integer maxSinglePathVal;
public PathValInfo(Integer maxPathVal, Integer maxSinglePathVal){
this.maxPathVal = maxPathVal;
this.maxSinglePathVal = maxSinglePathVal;
}
}
2.4 二叉搜索子树的最大键值和
题目描述：
给你一棵以 root 为根的 二叉树 ，请你返回 任意 二叉搜索子树的最大键值和。
思路：
1.最大键值和的可能性
- p1: 和x无关，右树的最大bst键值和，就是二叉搜索子树的最大键值和
- p2: 和x无关，左树的最大bst键值和，就是二叉搜索子树的最大键值和
- p3: 和x有关，左树整棵树是bst，右树整棵树也是bst，且x整个树为bst，那么，右树的最大bst键值和 + 左树的最大bst键值和 + x.val 就是最大bst键值和
- p4: 和x有关，左树整棵树是bst，右树为null，且x整个树为bst，那么，左树的最大bst键值和 + x.val 就是最大bst键值和
- P5: 和x有关，右树整棵树是bst，左树为null，且x整个树为bst，那么，右树的最大bst键值和 + x.val 就是最大bst键值和
2.需要收集的信息
- 以任何节点作为root时的整棵树是否是bst，minValue， maxValue
- 以任何节点作为root时的整棵树的最大搜索子树的最大键值和：maxBstPathVal
3.逻辑
- 空节点返回null
- isBst: 左树isBst & x.val > 左树.maxValue & x.value < 右树.minValue
- maxBstPathVal = Max(p1,p2,p3,p4,p5)
public int maxSumBST(TreeNode root) {
BSTPathInfo info = process(root);
return info.isAllfs ? 0 : info.maxBstPathVal;
}
public class BSTPathInfo{
private boolean isBst;
private boolean isAllfs;
private int minValue;
private int maxValue;
private int maxBstPathVal;
public BSTPathInfo(boolean isBst, boolean isAllfs, int minValue, int maxValue, int maxBstPathVal) {
this.isBst = isBst;
this.isAllfs = isAllfs;
this.minValue = minValue;
this.maxValue = maxValue;
this.maxBstPathVal = maxBstPathVal;
}
}
public BSTPathInfo process(TreeNode treeNode){
//空节点返回null
if(treeNode == null){
return null;
}
//1.收集信息
BSTPathInfo leftInfo = process(treeNode.left);
BSTPathInfo rightInfo = process(treeNode.right);
//2.整合信息
if(leftInfo == null && rightInfo == null){
return new BSTPathInfo(true, treeNode.val< 0, treeNode.val, treeNode.val, treeNode.val);
}
if(leftInfo !=null && rightInfo != null){
boolean isBst = false;
if(leftInfo.isBst && rightInfo.isBst && treeNode.val > leftInfo.maxValue && treeNode.val < rightInfo.minValue){
isBst = true;
}
boolean isAllfs = false;
if(leftInfo.isAllfs && rightInfo.isAllfs && treeNode.val< 0){
isAllfs = true;
}
int minValue = Math.min(treeNode.val, Math.min(leftInfo.minValue, rightInfo.minValue));
int maxValue = Math.max(treeNode.val, Math.max(leftInfo.maxValue, rightInfo.maxValue));
//maxBstPathVal
int p1 = rightInfo.maxBstPathVal;
int p2 = leftInfo.maxBstPathVal;
int p3 = rightInfo.maxBstPathVal + leftInfo.maxValue + treeNode.val;
int maxBstPathVal = isBst ? Math.max(p1,Math.max(p2, p3)) : Math.max(p1,p2);
return new BSTPathInfo(isBst, isAllfs, minValue, maxValue, maxBstPathVal);
}
//左树不为null
if(rightInfo == null){
boolean isBst = false;
if(leftInfo.isBst && treeNode.val > leftInfo.maxValue){
isBst = true;
}
boolean isAllfs = false;
if(leftInfo.isAllfs && treeNode.val < 0){
isAllfs = true;
}
int minValue = Math.min(treeNode.val, leftInfo.minValue);
int maxValue = Math.max(treeNode.val, leftInfo.maxValue);
//maxBstPathVal
int p2 = leftInfo.maxBstPathVal;
int p4 = leftInfo.maxValue + treeNode.val;
int maxBstPathVal = isBst ? Math.max(p2, p4) : p2;
return new BSTPathInfo(isBst, isAllfs, minValue, maxValue, maxBstPathVal);
}
//右树不为null
boolean isBst = false;
if(rightInfo.isBst && treeNode.val < rightInfo.minValue){
isBst = true;
}
boolean isAllfs = false;
if(rightInfo.isAllfs && treeNode.val< 0){
isAllfs = true;
}
int minValue = Math.min(treeNode.val, rightInfo.minValue);
int maxValue = Math.max(treeNode.val, rightInfo.maxValue);
//maxBstPathVal
int p1 = rightInfo.maxBstPathVal;
int p5 = rightInfo.maxValue + treeNode.val;
int maxBstPathVal = isBst ? Math.max(p1, p5) : p1;
return new BSTPathInfo(isBst, isAllfs, minValue, maxValue, maxBstPathVal);
}
