算法：Java计算二叉树从根节点到叶子结点的最大路径和
要求从根节点到叶子结点的最大路径和，可以通过递归遍历二叉树来实现。对于二叉树中的每个节点，我们都可以考虑包含该节点的最大路径和。在递归的过程中，我们需要不断更新全局最大路径和。
具体的思路
-
递归函数设计： 设计一个递归函数，该函数的任务是计算包含当前节点的最大路径和。函数的返回值应该是从当前节点出发到任意叶子节点的最大路径和。
-
递归终止条件： 在递归函数中，需要处理递归的终止条件。当当前节点为 null 时，返回 0，表示空路径的和为 0。
-
递归计算左右子树的最大路径和： 对于当前节点，递归计算左右子树的最大路径和。如果子树的最大路径和为负数，可以选择不包含该子树，将其贡献值设为 0。
-
更新全局最大路径和： 在递归的过程中，不断更新全局最大路径和。全局最大路径和是包含当前节点值的最大路径和，可能由左子树、右子树和当前节点共同组成。
-
返回当前子树的最大路径和： 在递归函数的最后，返回当前子树的最大路径和。
代码示例
class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int val) {this.val = val;}
}public class MaxPathSum {int maxSum = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {if (root == null) {return 0;}// 递归计算左右子树的最大路径和int leftMax = Math.max(maxPathSum(root.left), 0);int rightMax = Math.max(maxPathSum(root.right), 0);// 更新全局最大路径和maxSum = Math.max(maxSum, root.val + leftMax + rightMax);// 返回当前子树的最大路径和（只能选择左子树或右子树）return root.val + Math.max(leftMax, rightMax);}public static void main(String[] args) {MaxPathSum solution = new MaxPathSum();// 构造一棵二叉树（示例）TreeNode root = new TreeNode(10);root.left = new TreeNode(2);root.right = new TreeNode(10);root.left.left = new TreeNode(20);root.left.right = new TreeNode(-15);root.right.right = new TreeNode(20);root.left.left.left = new TreeNode(-20);root.right.right.left = new TreeNode(3);root.right.right.right = new TreeNode(-4);int result = solution.maxPathSum(root);System.out.println("最大路径和: " + result);}
}
小结
这个实现中，maxPathSum 方法返回的是以当前节点为根的最大路径和。在递归的过程中，不断更新 maxSum 变量，最终得到整棵树的最大路径和。