[Swift]LeetCode124.二叉树中的最大路径和|BinaryTreeMaximumPathSum

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3]

       1
      / \
     2   3

输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

64ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func maxPathSum(_ root: TreeNode?) -> Int {
16         var result = Int.min
17         
18         DFS(root, &result)
19         
20         return result
21     }
22     
23     private func DFS(_ root: TreeNode?, _ result: inout Int) -> Int {
24         guard let root = root else {
25             return 0
26         }
27         
28         let left = max(0,DFS(root.left, &result))
29         let right = max(0,DFS(root.right, &result))
30         
31         result = max(result, left + right + root.val)
32         
33         return max(left, right) + root.val
34     }
35 }

88ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     private var maxValue = Int.min
16     
17     func maxPathSum(_ root: TreeNode?) -> Int {
18         guard let root = root else { return 0 }
19         
20         maxValue = root.val
21         getMaxValue(root)
22         return maxValue
23     }
24     
25     
26     @discardableResult
27     private func getMaxValue(_ root: TreeNode?) -> Int {
28         guard let root = root else { return Int.min }
29         
30         var leftValue = Int.min, rightValue = Int.min
31         if let left = root.left {
32             leftValue = getMaxValue(left)
33         }
34         if let right = root.right {
35             rightValue = getMaxValue(right)
36         }
37         
38         leftValue = leftValue > 0 ? leftValue : 0
39         rightValue = rightValue > 0 ? rightValue : 0
40         
41         if leftValue + root.val + rightValue > maxValue {
42             maxValue = leftValue + root.val + rightValue
43         }
44         
45         return max(leftValue, rightValue) + root.val
46     }
47 }

120ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func maxPathSum(_ root: TreeNode?) -> Int {
16         if root == nil {return 0}
17         var tmpMax = root!.val
18         maxChildPathSum(root, &tmpMax)
19         return tmpMax
20     }
21     
22     /**
23      * 计算二叉树子树的最大路径和以及整棵二叉树的最大路径和
24      * 子树路径必须以根结点开始，以树中某一结点结束
25      * 二叉树的最大路径和的路径，不必以根结点为开始结点
26      * @param : root 二叉树根结点
27      * @param : tmpMax 暂存整棵二叉树的最路径和的变量的地址
28      * @return : 子树的最大路径和
29      */ 
30     func maxChildPathSum(_ root: TreeNode?,_ tmpMax: inout Int) ->Int
31     {
32         if root == nil {return 0}
33         /* 计算左右子树的最大路径和 */
34         var leftMax:Int = maxChildPathSum(root!.left, &tmpMax)
35         var rightMax:Int = maxChildPathSum(root!.right, &tmpMax);
36          /* 尝试更新整棵二叉树的最大路径和 */ 
37         var tmp:Int = root!.val
38         if leftMax > 0 {tmp += leftMax}
39         if rightMax > 0 {tmp += rightMax}
40         if tmp > tmpMax {tmpMax = tmp}
41         /* 计算并返回子树的最大路径和 */
42         var maxRoot:Int = max(root!.val, max(root!.val + leftMax, root!.val + rightMax))
43         return maxRoot
44     }
45 }

224ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func maxPathSum(_ root: TreeNode?) -> Int {
16         if root == nil {
17             return 0
18         }
19         let root: TreeNode! = root
20         var result = root.val
21         let temp = nodeMaxSum(root, &result)
22         return result
23     }
24     
25     //路过该节点的最大路径和，不以其为根。
26     func nodeMaxSum(_ node: TreeNode?, _ result: inout Int) -> Int {
27         if node == nil {
28             return Int.min
29         }
30         let node: TreeNode! = node
31         let leftNode = nodeMaxSum(node.left, &result)
32         let rightNode = nodeMaxSum(node.right, &result)
33         var temp = node.val
34         temp += leftNode > 0 ? leftNode : 0
35         temp += rightNode > 0 ? rightNode : 0
36         //result是以其为根的。
37         result = max(result, temp)
38         //左右子树中最大的值(比0大)与node.val相加
39         return max(max(leftNode, rightNode), 0) + node.val
40     }
41 }