• Swift 算法實(shí)戰(zhàn)一(集合,字典,鏈表,棧,隊(duì)列等算法)
• Swift 算法實(shí)戰(zhàn)二(二叉樹、二分搜索)

前言

這是繼Swift 算法實(shí)戰(zhàn)一(集合,字典,鏈表,棧,隊(duì)列等算法)之后的又一篇文章，算是所學(xué)知識(shí)總結(jié)，也算是之后找工作的敲門磚。筆者這月月底要離職，即使目前這家公司給我加薪的條件，也不再想繼續(xù)留下了。

這篇文章主要涉及到二叉樹、二分搜索等相關(guān)，具體請看文章內(nèi)容。

一、二叉樹

不得不承認(rèn)實(shí)際開發(fā)中很少用到二叉樹相關(guān)的知識(shí)，但是面試過程中卻被問道的不少。

1.1 二叉樹的認(rèn)識(shí)

1.1.1 概念

二叉樹是 n (n >= 0)個(gè)結(jié)構(gòu)的有限集合,改集合或者為空集(稱為空二叉樹),或者有一個(gè)根節(jié)點(diǎn)和兩棵互不相交的、分別稱為根節(jié)點(diǎn)的左子樹和右子樹的二叉樹組成。

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 性質(zhì)

• 在二叉樹的第 i 層上有至多 2^( i-1) 個(gè)結(jié)點(diǎn) (i >= 1).
• 深度為 k 的二叉樹至多有 2^k - 1 個(gè)節(jié)點(diǎn)(k >= 1).
• 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 [log (2) n] + 1 ([x] 表示不大于x的最大整數(shù)) .

1.2 判斷是否為二叉查找樹

二叉查找樹的特點(diǎn)是：左子樹節(jié)點(diǎn)值都小于根節(jié)點(diǎn)的值，而右子樹節(jié)點(diǎn)值大于根節(jié)點(diǎn)值。那么問題就來了，給你一個(gè)二叉樹，怎么通過最簡單的方式，判斷是否是二叉查找樹。

對于解答上面這個(gè)問題，我們至少需要考慮到這兩種情況。首先，二叉樹但從定義上就能看出和遞歸有一定的關(guān)系，所以通常解決二叉樹的問題，第一反應(yīng)就是要和遞歸綁定在一起；其次，二叉樹節(jié)點(diǎn)有為空的情況，所以一般針對空二叉樹這種邊界條件要做一些額外處理；

具體判斷實(shí)現(xiàn)如下代碼，代碼中包含詳細(xì)注釋，以及調(diào)用實(shí)例展示。

    //根據(jù)根節(jié)點(diǎn)做判斷
    func isValidTree(root:ZWTreeNode?) -> Bool{
        return self.helper(node: root, min: nil, max: nil)
    }
    
    func helper(node:ZWTreeNode?,min:Int?,max:Int?) -> Bool {
        //對于空節(jié)點(diǎn)的處理
        guard let node = node else { return true }
        //右子樹要求大于根節(jié)點(diǎn)
        if let min = min ,node.val <= min {
            return false
        }
        //左節(jié)點(diǎn)要小于根節(jié)點(diǎn)
        if let max = max,node.val >= max {
            return false
        }
        //根據(jù)左右節(jié)點(diǎn)同時(shí)做判斷
        return helper(node:node.left,min:min,max:node.val) && helper(node:node.right,min:node.val,max:max)
    }

//方法調(diào)用
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))//結(jié)果為：true

1.3 二叉樹的深度

計(jì)算二叉樹的深度，同樣是只要知道根節(jié)點(diǎn)即可，同樣也要借助遞歸實(shí)現(xiàn)。

//實(shí)現(xiàn)
func treeDepth(root:ZWTreeNode?) -> Int {
    guard let root = root else {
        return 0
    }
    return max(treeDepth(root:root.left), treeDepth(root: root.right)) + 1
 }

//調(diào)用形式
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))//結(jié)果為：2

1.4 二叉樹的遍歷

1.4.1 三種遍歷方式

二叉樹的遍歷多種多樣,,三種常用的遍歷: 前序遍歷、中序遍歷、后續(xù)遍歷（主要依據(jù)根節(jié)點(diǎn)遍歷的先后順序而定義的）。

前序遍歷首先訪問根結(jié)點(diǎn)，然后前序遍歷左子樹，再前序遍歷右子樹。

前序遍歷

中序遍歷首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，再訪問根結(jié)點(diǎn)，最后遍歷右子樹。

中序遍歷

后序遍歷首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)。在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后遍歷根結(jié)點(diǎn)。

后序遍歷

1.4.2 前序遍歷實(shí)現(xiàn)

這里主要看一下如何借助棧來實(shí)現(xiàn)前序遍歷。實(shí)際上其他幾種遍歷方式筆者是沒有怎么看的。

代碼邏輯的思路就是先遍歷節(jié)點(diǎn)的左子節(jié)點(diǎn)，當(dāng)左子節(jié)點(diǎn)為空的時(shí)候，就進(jìn)行pop操作，獲取父節(jié)點(diǎn)，根據(jù)父節(jié)點(diǎn)獲取右子節(jié)點(diǎn)。

    func formerSequenceTraversal(root:ZWTreeNode?) -> [Int] {
        var arr = [Int]()
        var stack = [ZWTreeNode]()
        var node = root
        //代碼邏輯的思路就是先遍歷節(jié)點(diǎn)的左子節(jié)點(diǎn)，當(dāng)左子節(jié)點(diǎn)為空的時(shí)候，就進(jìn)行pop操作，獲取父節(jié)點(diǎn)，根據(jù)父節(jié)點(diǎn)獲取右子節(jié)點(diǎn)。
        while stack.isEmpty == false || node != nil{
            if node != nil {
                arr.append(node!.val)
                stack.append(node!)//push操作，進(jìn)入子節(jié)點(diǎn)
                node = node?.left
            }else{
                node = stack.removeLast().right//pop操作，返回上一節(jié)點(diǎn)
            }
        }
        return arr
    }

前序遍歷調(diào)用形式。

        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))//打印結(jié)果為：[2, 1, 4, 5, 3]

二、二分搜索

2.1 概念

一個(gè)有序數(shù)組中，如果查找某個(gè)特定的元素。可以先從中間的元素開始尋找，如果中間元素是要找的元素，直接返回；如果中間元素小于目標(biāo)元素，則目標(biāo)原始在大于中間元素的那一邊；如果中間元素大于目標(biāo)元素，則目標(biāo)元素在小于中間元素的那一邊。按照上面的三種情況無限的循環(huán)下去，最終就能找到目標(biāo)元素。算法的時(shí)間復(fù)雜度為O(logn)。

2.2 簡單實(shí)現(xiàn)

接下來看看如果在一個(gè) Int 型有升序數(shù)組中，檢測是否存在給定的目標(biāo)值。代碼如下。

     //實(shí)現(xiàn)代碼
    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
    }

//調(diào)用形式
let arr = [1,2,3,4,5,6,7,8]
 print(binarySearch(arr: arr, target: 2))//打印結(jié)果為:true

總的來說代碼實(shí)現(xiàn)起來比較簡單，但是要注意到一點(diǎn)絕對不寫寫成mid = (right + left) / 2,否則可能發(fā)生崩潰，因?yàn)楫?dāng)搜索結(jié)果在右邊范圍的時(shí)候可能出現(xiàn)越界的情況，最正確的寫法應(yīng)當(dāng)是mid = (right - left) / 2 + left。如果想獲取到目標(biāo)元素的下表也很簡單，只要簡單改寫一下即可。如下代碼，其中如果返回值為 -1 ，則表示不存在目標(biāo)元素。

    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
    }