-
Notifications
You must be signed in to change notification settings - Fork 0
/
110_balanced_binary_tree.swift
86 lines (76 loc) · 2.44 KB
/
110_balanced_binary_tree.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/**
* Definition for a binary tree node.
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init() { self.val = 0; self.left = nil; self.right = nil; }
* public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
* public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
* self.val = val
* self.left = left
* self.right = right
* }
* }
*/
class Solution {
func isBalanced(_ root: TreeNode?) -> Bool {
guard let root = root else {
return true
}
print("\ncheck if \(root.val) is balanced")
var leftCount = 0
var rightCount = 0
var isLeftBalanced = true
var isRightBalanced = true
if let left = root.left {
leftCount = 1 + getNumberOfChild(left)
}
if let right = root.right {
rightCount = 1 + getNumberOfChild(right)
}
print("isBalanced of \(root.val) ? - leftCount: \(leftCount); rightCount: \(rightCount)")
if abs(leftCount-rightCount) <= 1 {
if let left = root.left {
isLeftBalanced = isBalanced(left)
}
if let right = root.right {
isRightBalanced = isBalanced(right)
}
print("isBalanced of \(root.val) ? - left: \(isLeftBalanced); right: \(isRightBalanced)")
return isLeftBalanced && isRightBalanced
} else {
return false
}
}
private func getNumberOfChild (_ root: TreeNode?) -> Int {
guard let root = root else {
return 0
}
print("\ncheck number of child of \(root.val)")
var leftCount = 0
var rightCount = 0
if root.left != nil {
leftCount += 1
}
if root.right != nil {
rightCount += 1
}
if root.left == nil && root.right == nil {
print("no children")
return 0
}
if let left = root.left {
leftCount += getNumberOfChild(left)
}
if let right = root.right {
rightCount += getNumberOfChild(right)
}
print("getNumberOfChild of \(root.val) - leftCount: \(leftCount); rightCount: \(rightCount)")
if leftCount >= rightCount {
return leftCount
} else {
return rightCount
}
}
}