[Swift]LeetCode543.二叉树的直径|DiameterofBinaryTree

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

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

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

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

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

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

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

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

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

示例 :
给定二叉树

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

256ms

 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 diameterOfBinaryTree(_ root: TreeNode?) -> Int {
16         if root == nil {return 0}
17         // 求二叉树的直径
18         var d_l = diameterOfBinaryTree(root!.left)
19         var d_r = diameterOfBinaryTree(root!.right)
20         var height_l = getHeight(root!.left)
21         var height_r = getHeight(root!.right)
22         
23         var tmp1 = d_l > d_r ? d_l : d_r
24         var tmp2 = height_l + height_r 
25         return tmp1 > tmp2 ? tmp1 : tmp2
26     }
27     // 获得二叉树的最大深度
28     func getHeight(_ root: TreeNode?) -> Int
29     {
30         if root == nil {return 0}
31         var h_l = getHeight(root!.left)
32         var h_r = getHeight(root!.right)
33         return ((h_l > h_r) ? h_l :h_r) + 1
34     }
35 }

24ms

 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     
16     func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
17         
18         guard let node = root else {
19             
20             return 0
21         }
22                         
23         let (leftOnly, throughLeft) = diameterOfChild(node.left)
24         let (rightOnly, throughRight) = diameterOfChild(node.right)
25         var maxLengthWithoutRoot = max(leftOnly, rightOnly)
26         var maxLengthThroughRoot = throughLeft + throughRight
27                 
28         return max(maxLengthWithoutRoot, maxLengthThroughRoot)
29     }
30     
31     func diameterOfChild(_ child: TreeNode?) -> (Int, Int) {
32         
33         guard let node = child else {
34             
35             return (0, 0)
36         }
37         
38         let (leftOnly, throughLeft) = diameterOfChild(node.left)
39         let (rightOnly, throughRight) = diameterOfChild(node.right)
40                
41         let maxOnly = max(leftOnly, rightOnly)
42         let diameter = (max(throughLeft + throughRight, maxOnly), max(throughLeft, throughRight) + 1)
43         
44         return diameter
45     }
46 }

28ms

 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     var diameter = 0
16 
17     func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
18         if root == nil || (root?.left == nil && root?.right == nil) {
19             return 0
20         }
21         
22 //         var maxLeft = maxDepth(root?.left)
23 //         var maxRight = maxDepth(root?.right)
24         
25 //         return maxLeft + maxRight
26         
27         
28         maxDepth(root)
29         
30         return diameter
31     }
32     
33     func maxDepth(_ root: TreeNode?) -> Int {
34         if root == nil {
35             return 0
36         }
37         
38         if root?.left == nil && root?.right == nil {
39             return 1
40         }
41 
42         let leftDepth = maxDepth(root?.left)
43         let rightDepth = maxDepth(root?.right)
44         
45         diameter = max(diameter, leftDepth + rightDepth)
46         
47         return max(leftDepth,rightDepth) + 1
48     }
49 }

32ms

 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     
16     func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
17         
18         guard let node = root else {
19             
20             return 0
21         }
22                         
23         let (leftOnly, throughLeft) = diameterOfChild(node.left)
24         let (rightOnly, throughRight) = diameterOfChild(node.right)
25         var maxLengthWithoutRoot = max(leftOnly, rightOnly)
26         var maxLengthThroughRoot = throughLeft + throughRight
27                 
28         return max(maxLengthWithoutRoot, maxLengthThroughRoot)
29     }
30     
31     func diameterOfChild(_ child: TreeNode?) -> (Int, Int) {
32         
33         guard let node = child else {
34             
35             return (0, 0)
36         }
37         
38         let (leftOnly, throughLeft) = diameterOfChild(node.left)
39         let (rightOnly, throughRight) = diameterOfChild(node.right)
40                
41         let maxOnly = max(leftOnly, rightOnly)
42         let diameter = (max(throughLeft + throughRight, maxOnly), max(throughLeft, throughRight) + 1)
43         
44         return diameter
45     }
46 }

36ms

 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 diameterOfBinaryTree(_ root: TreeNode?) -> Int {
16         var res = 1
17         getSum(root, &res)
18         print(res)
19         return res - 1
20     }
21     
22     func getSum(_ root: TreeNode?, _ res: inout Int) -> Int {
23         
24         guard let val = root?.val else {
25             
26             return 0
27         }
28         
29         var left = getSum(root?.left, &res)
30         var right = getSum(root?.right, &res)
31         
32         res = max(res, (left + right + 1))
33         return max(left, right) + 1
34         
35     }
36 }

40ms

 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     var longestPath = 1
16     
17     func diameterOfBinaryTree(_ root: TreeNode?) -> Int {        
18         depth(root)
19         return longestPath - 1
20     }
21     
22     func depth(_ node: TreeNode?) -> Int {
23         if node == nil { return 0 }
24         let l = depth(node!.left)
25         let r = depth(node!.right)
26         longestPath = max(longestPath, l + r + 1)
27         return max(l, r) + 1
28     }
29 }

40ms

 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     var m : Int = 0
16     
17     func depth(_ root : TreeNode?) -> Int
18     {
19         if root == nil {
20             return 0
21         }
22         
23                     
24         let lft = depth(root!.left)
25             
26         let rit = depth(root!.right)
27         
28         m = max(m,rit + lft)
29         return max(lft,rit) + 1
30     }
31     
32     func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
33         if root == nil {
34             return 0
35         }
36 
37         depth(root)
38         
39         return m
40     }
41 }

44ms

 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 diameterOfBinaryTree(_ root: TreeNode?) -> Int {
16         guard let root = root else {
17             return 0
18         }
19         
20         var longestPath = 0
21         
22         depth(root, &longestPath)
23         
24         return longestPath
25     }
26     
27     func depth(_ root: TreeNode?, _ longestPath: inout Int) -> Int {
28         guard let root = root else { return 0 }
29         let leftDepth = depth(root.left, &longestPath)
30         let rightDepth = depth(root.right, &longestPath)
31         
32         longestPath = max(longestPath, rightDepth + leftDepth)
33         
34         return max(leftDepth, rightDepth) + 1
35 
36     }
37 }

48ms

 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 diameterOfBinaryTree(_ root: TreeNode?) -> Int {
16         var result = 0
17         _ = diameterOfBinaryTree(root, &result)
18         return result
19     }
20     
21     func diameterOfBinaryTree(_ root: TreeNode?, _ sum: inout Int) -> Int {
22         guard let root = root else {
23             return 0
24         }
25         
26         let left = diameterOfBinaryTree(root.left, &sum)
27         let right = diameterOfBinaryTree(root.right, &sum)
28         sum = max(sum, left + right)
29         
30         return 1 + max(left, right)
31     }
32 }

84ms

 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 diameterOfBinaryTree(_ root: TreeNode?) -> Int {
16         guard let root = root else { return 0 }
17         var longestPath = 0
18         
19         func maxDepth(_ root: TreeNode?) -> Int {
20             guard let root = root else { return 0 }
21             let lVal = maxDepth(root.left)
22             let rVal = maxDepth(root.right)
23             longestPath = max(longestPath, lVal + rVal)
24             return max(lVal, rVal) + 1
25         }
26         
27         maxDepth(root)
28         return longestPath
29     }
30 }

144ms

 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 diameterOfBinaryTree(_ root: TreeNode?) -> Int {
16         guard let root = root else { return 0 }
17         return max(depth(root.left) + depth(root.right), diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right))
18     }
19     
20     private func depth(_ root: TreeNode?) -> Int {
21         guard let root = root else { return 0 }
22         return 1 + max(depth(root.left), depth(root.right))
23     }
24 }

148ms

 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     
16     func diameterOfBinaryTree(_ root: TreeNode?) -> Int {
17         
18         guard let node = root else {
19             
20             return 0
21         }
22                         
23         let (leftOnly, throughLeft) = diameterOfChild(node.left)
24         let (rightOnly, throughRight) = diameterOfChild(node.right)
25         var maxLengthWithoutRoot = max(leftOnly, rightOnly)
26         var maxLengthThroughRoot = throughLeft + throughRight
27                 
28         return max(maxLengthWithoutRoot, maxLengthThroughRoot)
29     }
30     
31     func diameterOfChild(_ child: TreeNode?) -> (Int, Int) {
32         
33         guard let node = child else {
34             
35             return (0, 0)
36         }
37         
38         print("node \(node.val)")
39         let (leftOnly, throughLeft) = diameterOfChild(node.left)
40         let (rightOnly, throughRight) = diameterOfChild(node.right)
41                
42         print("leftOnly \(leftOnly) === throughLeft \(throughLeft)")
43         print("rightOnly \(rightOnly) === throughRight \(throughRight)")
44         
45         let maxOnly = max(leftOnly, rightOnly)
46         let diameter = (max(throughLeft + throughRight, maxOnly), max(throughLeft, throughRight) + 1)
47         print("diameter \(diameter)")
48         
49         return diameter
50     }
51 }

152ms

 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   
                       
                    
                     
                      



鲜花




握手




雷人




路过




鸡蛋