[Swift]LeetCode687.最长同值路径|LongestUnivaluePath

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

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

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

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

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

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

Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.

Note: The length of path between two nodes is represented by the number of edges between them.

Example 1:

Input:

Output:

Example 2:

Input:

Output:

Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。这条路径可以经过也可以不经过根节点。

注意：两个节点之间的路径长度由它们之间的边数表示。

示例 1:

输入:

输出:

示例 2:

输入:

输出:

注意: 给定的二叉树不超过10000个结点。树的高度不超过1000。

360ms

  1 class Solution 
  2 {    
  3     /* Wrapper Function */    
  4     func countUnivaluedTrees( _ rootNode: TreeNode ) -> Int 
  5     {
  6         var isUnivalue: Bool = true        
  7         let leftResult: Int
  8         let rightResult: Int        
  9         if let leftChild: TreeNode = rootNode.left
 10         {            
 11             leftResult = countUnivaluedTrees( leftChild )            
 12             if leftResult > 1 || rootNode.val != leftChild.val
 13             {                
 14                 isUnivalue = false                
 15             }            
 16         }
 17         else
 18         {            
 19             leftResult = 0            
 20         }
 21         
 22         if let rightChild: TreeNode = rootNode.right
 23         {            
 24             rightResult = countUnivaluedTrees( rightChild )            
 25             if rightResult > 1 || rootNode.val != rightChild.val
 26             {                
 27                 isUnivalue = false                
 28             }            
 29         }
 30         else
 31         {            
 32             rightResult = 0            
 33         }                
 34         if isUnivalue
 35         {            
 36             return 1            
 37         }
 38         else
 39         {            
 40             return ( leftResult + rightResult )            
 41         }        
 42     }
 43     
 44     /* Wrapper Function */    
 45     func longestUnivaluePath( _ root: TreeNode? ) -> Int 
 46     {
 47         /* Recursive Traversal 1 */        
 48         func traverseTreeR1( _ root: TreeNode ) 
 49         -> ( longestUnivaluedWalk: Int, longestUnivaluedPath: Int )
 50         {            
 51             /* Partial Results */            
 52             var childCount: Int = 0            
 53             var leftLongestUnivaluedWalk: Int = 0
 54             var rightlongestUnivaluedWalk: Int = 0            
 55             let longestUnivaluedWalk: Int
 56             let longestRootUnivaluedPath: Int            
 57             var longestUnivaluedPath: Int = 0
 58             
 59             /* Left Child */
 60             
 61             if let leftChild: TreeNode = root.left
 62             {                
 63                 childCount += 1                
 64                 let leftResult = traverseTreeR1( leftChild )                
 65                 if root.val == leftChild.val
 66                 {                    
 67                     leftLongestUnivaluedWalk = ( leftResult.longestUnivaluedWalk )                    
 68                 }                
 69                 longestUnivaluedPath = max( longestUnivaluedPath, leftResult.longestUnivaluedPath )                
 70             }
 71             
 72             /* Right Child */            
 73             if let rightChild: TreeNode = root.right
 74             {                
 75                 childCount += 1                
 76                 let rightResult = traverseTreeR1( rightChild )                
 77                 if root.val == rightChild.val
 78                 {                    
 79                     rightlongestUnivaluedWalk = ( rightResult.longestUnivaluedWalk )                    
 80                 }                
 81                 longestUnivaluedPath = max( longestUnivaluedPath, rightResult.longestUnivaluedPath )                
 82             }
 83             
 84             /* Construct Result */            
 85             longestUnivaluedWalk = 1 + max( leftLongestUnivaluedWalk, rightlongestUnivaluedWalk )
 86             longestRootUnivaluedPath = ( leftLongestUnivaluedWalk + rightlongestUnivaluedWalk + 1 )        
 87             longestUnivaluedPath = max( longestUnivaluedPath, longestRootUnivaluedPath )            
 88             return ( longestUnivaluedWalk, longestUnivaluedPath )            
 89         }
 90         
 91         /* Recursive Traversal 2 */        
 92         func traverseTreeR2( _ root: TreeNode ) 
 93         -> ( longestUnivaluedWalk: Int, longestUnivaluedPath: Int )
 94         {            
 95             var longestRootUnivaluedPath: Int = 1
 96             var longestUnivaluedWalk: Int = 1            
 97             var longestUnivaluedPath: Int = 1            
 98             if let left = root.left
 99             {                
100                 let leftResult = traverseTreeR2( left )                
101                 if root.val == left.val
102                 {                    
103                     longestRootUnivaluedPath += leftResult.longestUnivaluedWalk                 
104                     longestUnivaluedWalk = max( longestUnivaluedWalk, 1 + leftResult.longestUnivaluedWalk )                    
105                 }                
106                 longestUnivaluedPath = max( longestUnivaluedPath, leftResult.longestUnivaluedPath )                
107             }            
108             if let right = root.right
109             {                
110                 let rightResult = traverseTreeR2( right )                
111                 if root.val == right.val
112                 {                    
113                     longestRootUnivaluedPath += rightResult.longestUnivaluedWalk                 
114                     longestUnivaluedWalk = max( longestUnivaluedWalk, 1 + rightResult.longestUnivaluedWalk )
115                     
116                 }                
117                 longestUnivaluedPath = max( longestUnivaluedPath, rightResult.longestUnivaluedPath )                
118             }                   
119             longestUnivaluedPath = max( longestUnivaluedPath, longestRootUnivaluedPath )            
120             return ( longestUnivaluedWalk, longestUnivaluedPath )            
121         }
122         
123         /* Get Result */        
124         let result: Int        
125         if let root = root
126         {            
127             let traversalResult = traverseTreeR2( root )            
128             result = ( traversalResult.longestUnivaluedPath - 1 )            
129         }
130         else
131         {            
132             result = 0            
133         }        
134         return result        
135     }    
136 }

396ms

 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 longestUnivaluePath(_ root: TreeNode?) -> Int {
16         _ = longestUnivaluePathAtNode(root)
17         return result
18     }
19     
20     var result: Int = 0
21 
22 func longestUnivaluePathAtNode(_ root: TreeNode?) -> Int {
23     guard let root = root else {
24         return 0
25     }
26     
27     let left = longestUnivaluePathAtNode(root.left)
28     let right = longestUnivaluePathAtNode(root.right)
29     
30     var leftValue = 0 
31     var rightValue = 0 
32     if root.left != nil {
33         if root.val == root.left!.val {
34             leftValue = 1 + left 
35         }
36     }
37     
38     if root.right != nil {
39         if root.val == root.right!.val {
40             rightValue = 1 + right 
41         }
42     }
43    
44     result = max(result, leftValue + rightValue)
45     return max(leftValue, rightValue)
46   }
47 }

400ms

 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 longestUnivaluePath(_ root: TreeNode?) -> Int {
16         guard let root = root else {
17             return 0
18         }
19         
20         return length(root, val: root.val).maxLen
21     }
22     
23     private func length(_ node: TreeNode?, val: Int) -> (len: Int, maxLen: Int) {
24         guard let node = node else {
25             return (0,0)
26         }
27 
28         let left = length(node.left, val: node.val)
29         let right = length(node.right, val: node.val)
30         let maxLen = max(max(right.maxLen, left.len + right.len), max(left.maxLen, left.len + right.len))
31 
32         if node.val == val {
33             return (max(left.len, right.len) + 1, maxLen)
34         }
35 
36         return (0, maxLen)
37     }
38 }

428ms

 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 longestUnivaluePath(_ root: TreeNode?) -> Int {
16         var longest = 0
17         arrowLength(root, longest: &longest)
18         return longest
19     }
20 
21     func arrowLength(_ root: TreeNode?, longest: inout Int) -> Int {
22         guard let root = root else { return 0 }
23 
24         let leftLength = arrowLength(root.left, longest: &longest)
25         let rightLength = arrowLength(root.right, longest: &longest)
26         var leftArrow = 0, rightArrow = 0
27 
28         if let left = root.left, left.val == root.val {
29             leftArrow = leftLength + 1
30         }
31 
32         if let right = root.right, right.val == root.val {
33             rightArrow += rightLength + 1
34         }
35 
36         longest = max(longest, leftArrow + rightArrow)
37         return max(leftArrow, rightArrow)
38     }
39 }

440ms

 1 class Solution {
 2     
 3     var q = Queue()
 4     var longest = 0
 5     func longestUnivaluePath(_ root: TreeNode?) -> Int {
 6         guard let root = root else{
 7             return 0
 8         }
 9         q.enqueue(root)
10         
11         while(q.count != 0){
12             let node: TreeNode = q.dequeue()
13             let numEdge = FindPath(node, node, node.val, 0, 0)
14             if(numEdge > longest){
15                 longest = numEdge
16             }
17         }
18         return longest
19     }
20         
21     func FindPath(_ root: TreeNode, _ node: TreeNode, _ value: Int, _ leftSum: Int, _ rightSum: Int)->Int{
22         var leftSum = leftSum
23         var rightSum = rightSum
24         if let left = node.left {
25             if left.val == value{
26                 leftSum += FindPath(root, left, node.val, leftSum, 0) + 1    
27             }else{
28                 q.enqueue(left)
29             }
30         }
31         if let right = node.right{
32             if right.val == value{
33                 rightSum += FindPath(root, right, node.val, 0, rightSum) + 1    
34             }else{
35                 q.enqueue(right)
36             }
37 
38         }
39         
40         if(node !== root){
41             return max(leftSum, rightSum)
42         }else{
43             return leftSum + rightSum
44         }
45         
46     }
47         
48 }
49 
50 class Queue{
51     var ar = [TreeNode]()
52     var count: Int {
53         return ar.count
54     }
55     
56     func enqueue(_ n: TreeNode){
57         self.ar.append(n)
58     }
59     
60     func dequeue() -> TreeNode{
61         let node = ar[0]
62         self.ar.remove(at: 0)
63         return node
64     }
65 }

464ms

 1 class Solution {
 2     func longestPath(_ root: TreeNode?, _ ans: inout Int) -> Int {
 3         guard let node = root else { return 0 }
 4         
 5         let nodeLeft = longestPath(node.left, &ans)
 6         let nodeRight = longestPath(node.right, &ans)
 7                 
 8         var left = 0
 9         var right = 0
10         
11         if node.left != nil && node.left!.val == node.val {
12             left += nodeLeft + 1
13         }
14         if node.right != nil && node.right!.val == node.val {
15             right += nodeRight + 1
16         }
17          
18         ans = Swift.max(ans, left+right)
19         
20         return Swift.max(left, right)
21     }
22     
23     func longestUnivaluePath(_ root: TreeNode?) -> Int {
24         guard let node = root else { return 0 }
25         var ans = 0
26         
27         longestPath(node, &ans)
28         
29         return ans
30     }
31 }

484ms

 1 class Solution {
 2     func longestUnivaluePath(_ root: TreeNode?) -> Int {
 3         var longest = 0
 4         longestValHelper(root, longest: &longest)
 5         return longest
 6     }
 7 
 8     func longestValHelper(_ root: TreeNode?, longest: inout Int) {
 9 
10         guard let root = root else { return }
11         let left = maxVal(root.left, val: root.val)
12         let right = maxVal(root.right, val: root.val)
13         longest = max(left + right, longest)
14         longestValHelper(root.left, longest: &longest)
15         longestValHelper(root.right, longest: &longest)
16     }
17 
18     func maxVal(_ root: TreeNode?, val: Int) -> Int {
19         guard let root = root else { return 0 }
20 
21         if root.val == val {
22             return 1 + max(maxVal(root.left, val: val), maxVal(root.right, val: val))
23         } else {
24             return 0
25         }
26     }
27 }

Runtime: 512 ms

Memory Usage: 20.3 MB

 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 longestUnivaluePath(_ root: TreeNode?) -> Int {
16         if root == nil {return 0}
17         var sub:Int = max(longestUnivaluePath(root!.left), longestUnivaluePath(root!.right))
18         return max(sub, helper(root!.left, root!.val) + helper(root!.right, root!.val))
19     }
20     
21     func helper(_ node: TreeNode?,_ parent:Int) ->Int
22     {
23         if node == nil || node!.val != parent {return 0}
24         return 1 + max(helper(node!.left, node!.val), helper(node!.right, node!.val))
25     }
26 }