【Hot100】LeetCode—124. 二叉树中的最大路径和

---

• 题目连接：124. 二叉树中的最大路径和

---

1- 思路

• 理解 dfs 的返回值，为什么只能是 root.val+Math.max(left,right)
  • 因为遍历的过程中只能从上到下，选择一条路径

dfs深搜实现

• ① 终止条件：如果 root== null 则返回 0
• ② 递归公式
  • sum = root.val + left + right;
  • res = Math.max(res,sum)
• ③ 递归返回结果
  • 返回结果为root.val + Math.max(left,right)

---

2- 实现

⭐124. 二叉树中的最大路径和——题解思路

class Solution {int resSum = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {dfs(root);return resSum;}public int dfs(TreeNode root){// 结束if(root==null){return 0;}int left = dfs(root.left);int right = dfs(root.right);int sum = left+right+root.val;resSum = Math.max(resSum,sum);// 返回结果int output = 0;output = root.val + Math.max(left,right);if(output>0) return output;return 0;}
}

---

3- ACM 实现

public class maxPathSum {public static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) {this.val = val;}TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}}public static TreeNode build(String str) {if (str == null || str.length() == 0) {return null;}String input = str.replace("[", "");input = input.replace("]", "");String[] parts = input.split(",");Integer[] nums = new Integer[parts.length];for (int i = 0; i < parts.length; i++) {if (!parts[i].equals("null")) {nums[i] = Integer.parseInt(parts[i]);} else {nums[i] = null;}}Queue<TreeNode> queue = new LinkedList<>();TreeNode root = new TreeNode(nums[0]);queue.offer(root);int index = 1;while (!queue.isEmpty() && index < parts.length) {TreeNode node = queue.poll();if (index < nums.length && nums[index] != null) {node.left = new TreeNode(nums[index]);queue.offer(node.left);}index++;if (index < nums.length && nums[index] != null) {node.right = new TreeNode(nums[index]);queue.offer(node.right);}index++;}return root;}static int res = Integer.MIN_VALUE;public static int maxP(TreeNode root){if(root==null){return 0;}// 计算int left = maxP(root.left);int right = maxP(root.right);int sum = left+right+root.val;res = Math.max(res,sum);// 返回值int output = 0;output = root.val + Math.max(left,right);if(output>0) return output;return 0;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String input = sc.nextLine();TreeNode root = build(input);maxP(root);System.out.println("结果是"+res);}
}