前言
這是繼Swift 算法實戰(zhàn)一(集合,字典,鏈表,棧,隊列等算法)之后的又一篇文章苍糠，算是所學知識總結雅镊，也算是之后找工作的敲門磚。筆者這月月底要離職捺信，即使目前這家公司給我加薪的條件酌媒，也不再想繼續(xù)留下了。
這篇文章主要涉及到二叉樹迄靠、二分搜索等相關秒咨，具體請看文章內容。
一掌挚、二叉樹
不得不承認實際開發(fā)中很少用到二叉樹相關的知識陡厘，但是面試過程中卻被問道的不少。
1.1 二叉樹的認識
1.1.1 概念
二叉樹是 n (n >= 0)個結構的有限集合,改集合或者為空集(稱為空二叉樹),或者有一個根節(jié)點和兩棵互不相交的、分別稱為根節(jié)點的左子樹和右子樹的二叉樹組成。
public class ZWTreeNode {
public var val: Int
public var left: ZWTreeNode?
public var right: ZWTreeNode?
public init(val: Int) {
self.val = val
}
}
1.1.2 性質
- 在二叉樹的第 i 層上有至多 2^( i-1) 個結點 (i >= 1).
- 深度為 k 的二叉樹至多有 2^k - 1 個節(jié)點(k >= 1).
- 具有n個結點的完全二叉樹的深度為 [log (2) n] + 1 ([x] 表示不大于x的最大整數) .
1.2 判斷是否為二叉查找樹
二叉查找樹的特點是：左子樹節(jié)點值都小于根節(jié)點的值，而右子樹節(jié)點值大于根節(jié)點值。那么問題就來了，給你一個二叉樹，怎么通過最簡單的方式，判斷是否是二叉查找樹。
對于解答上面這個問題，我們至少需要考慮到這兩種情況。首先铸磅，二叉樹但從定義上就能看出和遞歸有一定的關系弧械，所以通常解決二叉樹的問題界轩，第一反應就是要和遞歸綁定在一起；其次浊猾，二叉樹節(jié)點有為空的情況抖甘，所以一般針對空二叉樹這種邊界條件要做一些額外處理；
具體判斷實現如下代碼葫慎，代碼中包含詳細注釋衔彻，以及調用實例展示。
//根據根節(jié)點做判斷
func isValidTree(root:ZWTreeNode?) -> Bool{
return self.helper(node: root, min: nil, max: nil)
}
func helper(node:ZWTreeNode?,min:Int?,max:Int?) -> Bool {
//對于空節(jié)點的處理
guard let node = node else { return true }
//右子樹要求大于根節(jié)點
if let min = min ,node.val <= min {
return false
}
//左節(jié)點要小于根節(jié)點
if let max = max,node.val >= max {
return false
}
//根據左右節(jié)點同時做判斷
return helper(node:node.left,min:min,max:node.val) && helper(node:node.right,min:node.val,max:max)
}
//方法調用
let leftNode = ZWTreeNode(val: 1)
let rightNode = ZWTreeNode(val: 3)
let root = ZWTreeNode(val: 2)
root.left = leftNode
root.right = rightNode
print(isValidTree(root: root))//結果為：true
1.3 二叉樹的深度
計算二叉樹的深度偷办，同樣是只要知道根節(jié)點即可艰额，同樣也要借助遞歸實現。
//實現
func treeDepth(root:ZWTreeNode?) -> Int {
guard let root = root else {
return 0
}
return max(treeDepth(root:root.left), treeDepth(root: root.right)) + 1
}
//調用形式
let leftNode = ZWTreeNode(val: 1)
let rightNode = ZWTreeNode(val: 3)
let root = ZWTreeNode(val: 2)
root.left = leftNode
root.right = rightNode
print(treeDepth(root: root))//結果為：2
1.4 二叉樹的遍歷
1.4.1 三種遍歷方式
二叉樹的遍歷多種多樣,,三種常用的遍歷: 前序遍歷椒涯、中序遍歷柄沮、后續(xù)遍歷（主要依據根節(jié)點遍歷的先后順序而定義的）。
前序遍歷首先訪問根結點废岂，然后前序遍歷左子樹铡溪，再前序遍歷右子樹。
前序遍歷
中序遍歷首先遍歷左子樹泪喊，然后訪問根結點棕硫，最后遍歷右子樹。在遍歷左袒啼、右子樹時哈扮，仍然先遍歷左子樹，再訪問根結點蚓再，最后遍歷右子樹滑肉。
中序遍歷
后序遍歷首先遍歷左子樹，然后遍歷右子樹摘仅，最后訪問根結點靶庙。在遍歷左、右子樹時娃属，仍然先遍歷左子樹六荒，然后遍歷右子樹护姆，最后遍歷根結點。
后序遍歷
1.4.2 前序遍歷實現
這里主要看一下如何借助棧來實現前序遍歷掏击。實際上其他幾種遍歷方式筆者是沒有怎么看的卵皂。
代碼邏輯的思路就是先遍歷節(jié)點的左子節(jié)點，當左子節(jié)點為空的時候砚亭，就進行pop操作灯变，獲取父節(jié)點，根據父節(jié)點獲取右子節(jié)點捅膘。
func formerSequenceTraversal(root:ZWTreeNode?) -> [Int] {
var arr = [Int]()
var stack = [ZWTreeNode]()
var node = root
//代碼邏輯的思路就是先遍歷節(jié)點的左子節(jié)點添祸，當左子節(jié)點為空的時候，就進行pop操作寻仗，獲取父節(jié)點膝捞，根據父節(jié)點獲取右子節(jié)點。
while stack.isEmpty == false || node != nil{
if node != nil {
arr.append(node!.val)
stack.append(node!)//push操作愧沟，進入子節(jié)點
node = node?.left
}else{
node = stack.removeLast().right//pop操作蔬咬，返回上一節(jié)點
}
}
return arr
}
前序遍歷調用形式。
let subLeftLeftNode = ZWTreeNode(val: 4)
let subLeftRightNode = ZWTreeNode(val: 5)
let leftNode = ZWTreeNode(val: 1)
leftNode.left = subLeftLeftNode
leftNode.right = subLeftRightNode
let rightNode = ZWTreeNode(val: 3)
let root = ZWTreeNode(val: 2)
root.left = leftNode
root.right = rightNode
print(formerSequenceTraversal(root: root))//打印結果為：[2, 1, 4, 5, 3]
二沐寺、二分搜索
2.1 概念
一個有序數組中林艘，如果查找某個特定的元素』煳耄可以先從中間的元素開始尋找狐援，如果中間元素是要找的元素，直接返回究孕；如果中間元素小于目標元素啥酱，則目標原始在大于中間元素的那一邊；如果中間元素大于目標元素厨诸，則目標元素在小于中間元素的那一邊镶殷。按照上面的三種情況無限的循環(huán)下去，最終就能找到目標元素微酬。算法的時間復雜度為O(logn)绘趋。
2.2 簡單實現
接下來看看如果在一個 Int 型有升序數組中，檢測是否存在給定的目標值颗管。代碼如下陷遮。
//實現代碼
func binarySearch(arr: [Int], target: Int) -> Bool {
var left = 0
var mid = 0
var right = arr.count - 1
while left <= right {
mid = (right - left) / 2 + left
if arr[mid] == target {
return true
} else if arr[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return false
}
//調用形式
let arr = [1,2,3,4,5,6,7,8]
print(binarySearch(arr: arr, target: 2))//打印結果為:true
總的來說代碼實現起來比較簡單，但是要注意到一點絕對不寫寫成mid = (right + left) / 2,否則可能發(fā)生崩潰垦江，因為當搜索結果在右邊范圍的時候可能出現越界的情況帽馋，最正確的寫法應當是mid = (right - left) / 2 + left。如果想獲取到目標元素的下表也很簡單，只要簡單改寫一下即可绽族。如下代碼姨涡，其中如果返回值為 -1 ，則表示不存在目標元素项秉。
func binarySearch(arr: [Int], target: Int) -> Int {
var left = 0
var mid = 0
var right = arr.count - 1
while left <= right {
mid = (right - left) / 2 + left
if arr[mid] == target {
return mid
} else if arr[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
