左神算法之二叉树最大路径和问题

二叉树最大路径和问题（Java实现）

1. 题目描述

给定一棵二叉树，其中每个节点都包含一个整型权值。要求计算从根节点到叶节点的所有路径中，权值和最大的值是多少。

2. 问题解释

• 必须从根节点出发到叶子节点结束
• 需要遍历所有可能的路径
• 找出所有路径和中最大的那个值
• 叶子节点是指没有子节点的节点

3. 解决思路

采用深度优先搜索（DFS）递归方法：

1. 如果当前节点是null，返回0（虽然题目保证有根节点，但递归时需要处理）
2. 如果是叶子节点，返回节点值本身
3. 递归计算左右子树的最大路径和
4. 返回当前节点值加上左右子树中较大的那个和

4. 代码实现

public class Problem07_MaxSumInTree {public static class Node {public int value;public Node left;public Node right;public Node(int data) {value = data;}}public static int maxSum = Integer.MIN_VALUE;public static int maxSum(Node head) {p(head, 0);return maxSum;}public static void p(Node head, int pre) {if (head == null) {return;}if (head.left == null && head.right == null) {maxSum = Math.max(maxSum, pre + head.value);}if (head.left != null) {p(head.left, pre + head.value);}if (head.right != null) {p(head.right, pre + head.value);}}// 另一种方式public static int maxSum2(Node head) {if (head == null) {return 0;}return process2(head);}public static int process2(Node head) {if (head == null) {return 0;}if(head.left == null && head.right == null){return head.value;}int next = Integer.MIN_VALUE;if(head.left != null){next = process2(head.left);}if(head.right != null){next = Math.max(next, process2(head.right));}return head.value + next;}public static void main(String[] args) {// 构建示例二叉树//         1//      /   \//     2     3//    / \   / \//   4   5 6   7Node head = new Node(1);head.left = new Node(2);head.right = new Node(3);head.left.left = new Node(4);head.left.right = new Node(5);head.right.left = new Node(6);head.right.right = new Node(7);System.out.println(maxSum(head));	 // 11System.out.println(maxSum2(head)); 	// 11}}

5. 总结

1. 使用DFS递归方法简洁高效
2. 时间复杂度：O(n)，需要访问所有节点
3. 空间复杂度：O(h)，h为树的高度，递归调用栈的深度
4. 注意处理叶子节点和空节点的情况
5. 该方法只能用于计算根到叶的路径和，不是任意节点间的最大路径和