124.二叉树中的最大路径和

linwt · linwt · commit 06bb337db030 · 2022-04-10T11:44:13.000+08:00
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -46,6 +46,7 @@
 121. 买卖股票的最佳时机
 122. 买卖股票的最佳时机 II
 123. 买卖股票的最佳时机 III
+124. 二叉树中的最大路径和
 130. 被围绕的区域
 131. 分割回文串
 136. 只出现一次的数字
diff --git a/leetcode_Java/Solution0124.java b/leetcode_Java/Solution0124.java
@@ -0,0 +1,47 @@
+// 124. 二叉树中的最大路径和
+
+
+/**
+ * Definition for a binary tree node.
+ * public 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;
+ *     }
+ * }
+ */
+
+
+/*
+递归：
+1、方法功能：入参是一个节点，返回该节点给父节点的贡献值
+2、终止条件：空节点时返回0
+3、单层递归逻辑：
+  1）调用递归方法得到左节点、右节点的贡献值
+  2）计算当前节点为路径根节点时的最大路径和，并更新最大结果。最大路径和 = 根节点值 + 左节点值 + 右节点值
+  3）计算当前节点给父节点的贡献值，若为负数则记为0，并返回贡献值。贡献值 = max(0, 根+左, 根+右)
+ */
+class Solution {
+    int res = Integer.MIN_VALUE;
+
+    public int maxPathSum(TreeNode root) {
+        dfs(root);
+        return res;
+    }
+
+    private int dfs(TreeNode root) {
+        if (root == null) {
+            return 0;
+        }
+        int left = dfs(root.left);
+        int right = dfs(root.right);
+        res = Math.max(res, root.val + left + right);
+        return Math.max(0, Math.max(root.val + left, root.val + right));
+    }
+}
