[Swift]LeetCode110.平衡二叉树|BalancedBinaryTree

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

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

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

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

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

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

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example 1:

Given the following tree [3,9,20,null,null,15,7]:

Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

Return false.

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

返回 false 。

 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 isBalanced(_ root: TreeNode?) -> Bool {
16         //递归分治法
17         if root == nil {return true}
18         
19         var depthLeft:Int = depth(root?.left)
20         var depthRight:Int = depth(root?.right)
21         if abs(depthLeft-depthRight) > 1
22         {
23             return false
24         }
25         else
26         {
27             return isBalanced(root?.left) && isBalanced(root?.right)
28         }
29     }
30     //求树的高度
31     func depth(_ n:TreeNode?)->Int
32     {
33         if n==nil
34         {
35             return 0
36         }
37         else if n?.left == nil && n?.right == nil
38         {
39             return 1
40         }
41         else
42         {
43             var depthLeft:Int = depth(n?.left)
44             var depthRight:Int = depth(n?.right)
45             return (1 + ((depthLeft > depthRight) ? depthLeft : depthRight))
46         }       
47     }
48 }

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     
16 //     func isBalanced(_ root: TreeNode?) -> Bool {
17 //         guard let root = root else {
18 //             return true
19 //         }
20 //         if abs(getDepth(root.left) - getDepth(root.right)) > 1 {
21 //             return false
22 //         }
23 //         return isBalanced(root.left) && isBalanced(root.right)
24 //     }
25     
26 //     func getDepth(_ root: TreeNode?) -> Int {
27 //         if root == nil {
28 //             return 0
29 //         }
30 //         return max(getDepth(root!.left), getDepth(root!.right)) + 1
31 //     }
32     
33     func isBalanced(_ root: TreeNode?) -> Bool {
34         if checkDepth(root) == -1 {
35             return false
36         }
37         return true
38     }
39     
40     func checkDepth(_ root: TreeNode?) -> Int {
41         guard let root = root else {
42             return 0
43         }
44         
45         let left = checkDepth(root.left)
46         if left == -1 {
47             return -1
48         }
49         
50         let right = checkDepth(root.right)
51         if right == -1 {
52             return -1
53         }
54         
55         if abs(left - right) > 1 {
56             return -1
57         }
58         
59         return max(left, right) + 1
60     }
61 }

52ms

 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 isBalanced(_ root: TreeNode?) -> Bool {
16         var result = true
17         isBalanced(root, &result)
18         return result
19     }
20     
21     func isBalanced(_ root: TreeNode?, _ result: inout Bool) -> Int {
22         guard let root = root else {
23             return 0
24         }
25         
26         guard result else {
27             return 0
28         }
29         
30         let leftHeight = isBalanced(root.left, &result)
31         let rightHeight = isBalanced(root.right, &result)
32         if abs(leftHeight - rightHeight) > 1 {
33             result = false
34         }
35         
36         return 1 + max(leftHeight, rightHeight)
37     }
38 }

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     func isBalanced(_ root: TreeNode?) -> Bool {
16         return root?.depth() != Int.max
17     }
18     
19 }
20 
21 extension TreeNode {
22     func depth(withPreviousDepth depth : Int = 1) -> Int {
23         let leftDepth = self.left?.depth(withPreviousDepth: depth + 1) ?? depth
24         let rightDepth = self.right?.depth(withPreviousDepth: depth + 1) ?? depth
25         
26         // looks repetitive, but it has better real-world
27         // runtime performance than using max() and abs()
28         if (leftDepth > rightDepth) {
29             guard leftDepth - rightDepth <= 1 else { return Int.max }
30             return leftDepth
31         } else {
32             guard rightDepth - leftDepth <= 1 else { return Int.max }
33             return rightDepth
34         }
35     }
36 }

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 isBalanced(_ root: TreeNode?) -> Bool {
16         return dfs(root) != -1
17     }
18     
19     func dfs(_ node: TreeNode?) -> Int {
20       
21         if node == nil {
22             return 0
23         }
24         
25         let leftHeight = dfs(node?.left)
26         
27         if leftHeight == -1 {
28             return -1
29         }
30         
31         let rightHeight = dfs(node?.right)
32         
33         if rightHeight == -1 {
34             return -1
35         }
36         
37         let totalHeight = abs(leftHeight - rightHeight)
38         
39         if totalHeight > 1 {
40             return -1
41         }
42         
43         return max(leftHeight, rightHeight) + 1
44     }
45     
46 }