數(shù)據(jù)結構基礎--二叉樹

本文主要作為自己的學習筆記官份，并不具備過多的指導意義妹萨。

基本概念
二叉樹的重點
二叉樹的遍歷
實現(xiàn)先序遍歷
實現(xiàn)中序遍歷
實現(xiàn)后序遍歷
以每層換行的方式進行廣度遍歷
二叉樹的序列化和反序列化
前序遍歷的歸檔&&解歸檔
廣度遍歷歸檔&&解歸檔
二叉樹的子樹
平衡二叉樹(AVL樹)
搜索二叉樹
滿二叉樹
完全二叉樹
后序節(jié)點與前驅(qū)節(jié)點
二叉樹中兩節(jié)點間的距離
參考資料

基本概念

基本結構

本節(jié)點的值，左子節(jié)點朗伶，右子節(jié)點。（以及一個初始化賦值）

public class TreeNode {
  public var val: Int
  public var left: TreeNode?
  public var right: TreeNode?
  public init(_val: Int) {
    self.val = val
  }
}

二叉樹的重點

能夠結合隊列艇潭，棧回还，鏈表裆泳，字符串等很多數(shù)據(jù)結構出題。
基本遍歷方式：比如BFS（廣度）柠硕，DFS（深度）工禾。
遞歸的使用

二叉樹的遍歷

先序，中序蝗柔，后序遍歷為最常見的樹的三種遍歷方式闻葵。這三種寫法相似，無非是遞歸的順序略有不同癣丧。

先序遍歷

先序遍歷先從二叉樹的根開始槽畔，然后到左子樹，再到右子樹胁编。

遍歷的結果是：ABDCEF

中序遍歷

中序遍歷先從左子樹開始厢钧，然后到根，再到右子樹嬉橙。

遍歷的結果是：DBAECF

后續(xù)遍歷

后序遍歷先從左子樹開始早直，然后到右子樹，再到根憎夷。

遍歷的結果是：DBEFCA

實現(xiàn)先序遍歷

遞歸

打印自己，然后先遍歷左節(jié)點再遍歷右節(jié)點

/// 先序遍歷--遞歸
///
/// - Parameter node: 遍歷節(jié)點
func preorderRecur(node: TreeNode?) {
    if node == nil {
        return
    }
    
    print(node!.val)//打印當前節(jié)點
    preorderRecur(node: node!.left)//遍歷左節(jié)點
    preorderRecur(node: node!.right)//遍歷右節(jié)點
}

非遞歸

先嘗試將左元素入棧昧旨，若棧頂元素為空則將棧頂推出然后嘗試遍歷右節(jié)點拾给。直到棧為空則遍歷結束。

這里的棧用處是為了保存二叉樹的結構兔沃，以彌補二叉樹無法獲取父節(jié)點的結構特性蒋得。

/// 先序遍歷--while
///
/// - Parameter root: 根節(jié)點
/// - Returns: 遍歷結果數(shù)組
func preorderTraversals(root: TreeNode?) -> [Int] {
    var res = [Int]()
    var stack = [TreeNode]() //遍歷用的棧
    var node = root//遍歷的根節(jié)點
    
    while !stack.isEmpty || node != nil {
        if node != nil {
            res.append(node!.val)  //將當前節(jié)點的值記錄
            stack.append(node!) //將當前節(jié)點加入棧中
            node = node!.left //嘗試遍歷當前節(jié)點的左節(jié)點
        } else {
            let parentsNode = stack.removeLast() //取出當前節(jié)點的父節(jié)點
            node = parentsNode.right  //將棧頂節(jié)點推出，并嘗試遍歷其父元素的右節(jié)點乒疏。
        }
    }
    
    return res
}

還有一種方式

這種方式純粹的利用棧的性質(zhì)额衙，每次彈出棧頂元素，并嘗試將其左右孩子入棧怕吴。

不過需要注意的是后入棧的為左孩子窍侧，以保證優(yōu)先遍歷左側。

func preorderTraversal(root: TreeNode?) -> [Int] {
    var res = [Int]()
    var stack = [TreeNode]() //遍歷用的棧
    var node = root//遍歷的根節(jié)點
    stack.append(root!)
    
    while !stack.isEmpty{

        res.append(stack.last!.val)
        node = stack.removeLast()
        if node!.right != nil {
            stack.append(node!.right!)
        }
        
        if node!.left != nil {
             stack.append(node!.left!)
        }
    }
    
    return res
}

實現(xiàn)中序遍歷

遞歸

/// 中序遍歷--遞歸
///
/// - Parameter node: 遍歷節(jié)點
func inorderRecur(node: TreeNode?) {
    if node == nil {
        return
    }
    
    inorderRecur(node: node!.left)//遍歷左節(jié)
    print(node!.val)//打印當前節(jié)點
    inorderRecur(node: node!.right)//遍歷右節(jié)點
}

非遞歸

與前序遍歷相同转绷，只是記錄的時間不一樣了

func inorderTraversal(root: TreeNode?) -> [Int] {
    var res = [Int]()
    var stack = [TreeNode]()
    var node = root
    
    while !stack.isEmpty || node != nil {
        if node != nil {
            stack.append(node!) //將當前節(jié)點依次入棧
            node = node!.left //嘗試遍歷左節(jié)點
        } else {
            let parentsNode = stack.removeLast() //取出當前節(jié)點的父節(jié)點
            res.append(parentsNode.val) //打印父節(jié)點
            node = parentsNode.right //嘗試遍歷右節(jié)點
        }
    }
    
    return res
}

先序遍歷與中序遍歷的非遞歸實現(xiàn)都是嘗試分解左邊界的過程

實現(xiàn)后序遍歷

遞歸

/// 后序遍歷--遞歸
///
/// - Parameter node: 遍歷節(jié)點
func posorderRecur(node: TreeNode?) {
    if node == nil {
        return
    }
    
    posorderRecur(node: node!.left)//嘗試遍歷左節(jié)
    posorderRecur(node: node!.right)//嘗試遍歷右節(jié)點
    print(node!.val)//打印當前節(jié)點
}

非遞歸

用兩個棧來實現(xiàn)伟件。

第一個棧的處理順序為，自上而下议经，自右而左斧账。經(jīng)過第二個棧的逆序谴返，就變成了自下而上，自左而右咧织。

另一種非遞歸

與之前兩種遍歷方式不同嗓袱，我們需要引入一個新的變量lastPrint來記錄最后一次打印的節(jié)點。以此判斷左习绢，右節(jié)點是否已經(jīng)被打印渠抹。

func posorderTraversal(root: TreeNode?) -> [Int] {
    if root == nil {
        return []
    }
    var res = [Int]()
    var stack = [TreeNode]()
    var node = root
    var lastPrint : TreeNode? //最后一次打印的節(jié)點
    stack.append(node!)


    while !stack.isEmpty{
        node = stack.last
        if node?.left != nil && node?.left != lastPrint && node?.right != lastPrint{
            stack.append((node?.left)!) //node的左子樹一定沒有打印完畢
        }else if node?.right != nil && node?.right != lastPrint {
            stack.append((node?.right)!)  //node的右子樹一定沒有打印完畢
        }else {
            //node的左右子樹全部打印完畢，尋找其父節(jié)點
            res.append(stack.last!.val)
            lastPrint = stack.removeLast()
        }
    }
    
    return res
}

以每層換行的方式進行廣度遍歷

層數(shù)變換的記錄毯炮，需要兩個變量逼肯。當前行最右節(jié)點(last)以及下一行最右(nlast)。

具體操作上

每次將新節(jié)點加入隊列時桃煎，將nlast更新成新節(jié)點篮幢。
當當前打印的節(jié)點等于last，執(zhí)行換行并將last更新到下一行nlast为迈。

代碼實現(xiàn)

func BFSTraversal(root: TreeNode?) -> String {
    
    if root == nil {
        return ""
    }
    
    var res = ""
    var queue = [TreeNode]()
    var last = root
    var nlast = root
    queue.append(root!)
    
    while !queue.isEmpty {
        let node = queue.removeFirst() //將隊首節(jié)點出隊
        res += node.val.description + " " //打印隊首節(jié)點
        
        if node.left != nil { //嘗試將左節(jié)點入隊
            queue.append(node.left!)
            nlast = node.left!
        }
        
        if node.right != nil { //嘗試將右節(jié)點入隊
            queue.append(node.right!)
            nlast = node.right!
        }
        
        if node == last { //換行
            last = nlast
            res += "\n"
        }
    }
    
    return res
}

二叉樹的序列化和反序列化

序列化方式

先序遍歷序列化
中序遍歷序列化
后序遍歷序列化
按層遍歷序列化

一棵樹序列化的結果和反序列化生成的二叉樹都是唯一的
序列化和遍歷二叉樹的區(qū)別

序列化時需要轉(zhuǎn)化成字符串三椿，所以每個節(jié)點之間需要用符號進行分割
序列化時需要記錄空節(jié)點，需要特殊符號進行記錄

舉個例子(用!分割葫辐，用#表空):

//序列化
5!12!20!#!#!22!#!#!17!21!#!#!23!#!33!40!#!#!
//遍歷
[5, 12, 20, 22, 17, 21, 23, 33, 40]

反序列化

將序列化字符串轉(zhuǎn)化成數(shù)組(比如這里通過!分割)

//字符串
5!12!20!#!#!22!#!#!17!21!#!#!23!#!33!40!#!#!
//數(shù)組
["5", "12", "20", "#", "#", "22", "#", "#", "17", "21", "#", "#", "23", "#", "33", "40", "#", "#"]

前序遍歷的歸檔&&解歸檔

歸檔

/// 先序遍歷歸檔--遞歸
///
/// - Parameter node: 遍歷節(jié)點
func preorderRecurArchive(node: TreeNode?) -> String {
    if node == nil {
        return "#!"
    }
    
    var res = (node?.val.description)! + "!"
    res += preorderRecurArchive(node: node!.left)//遍歷左節(jié)點
    res += preorderRecurArchive(node: node!.right)//遍歷右節(jié)點
    
    return res
}


/// 先序遍歷格式化--while
///
/// - Parameter root: 根節(jié)點
/// - Returns: 序列化字符串
func preorderArchive(root: TreeNode?) -> String {
    var res = ""
    var stack = [TreeNode]() //遍歷用的棧
    var node = root//遍歷的根節(jié)點
    
    while !stack.isEmpty || node != nil {
        if node != nil {
            res += node!.val.description + "!" //將當前節(jié)點的值記錄
            stack.append(node!) //將當前節(jié)點加入棧中
            node = node!.left //嘗試遍歷當前節(jié)點的左節(jié)點
        } else {
            let parentsNode = stack.removeLast() //取出當前節(jié)點的父節(jié)點
            node = parentsNode.right  //將棧頂節(jié)點推出搜锰，并嘗試遍歷其父元素的右節(jié)點。
            res += "#!" //記錄空節(jié)點
        }
    }
    res += "#!" //記錄空節(jié)點
    return res
}

解歸檔

遞歸

/// 前序遍歷解歸檔--遞歸
///
/// - Parameter str: 歸檔字符串
/// - Returns: 頭節(jié)點
func preorderRecurRearchive(str: String?) -> TreeNode? {
    var treeQueue = (str?.components(separatedBy: "!"))!
    treeQueue.removeLast() //這里切割完畢之后最后數(shù)組的最后一位為""
    
    return preorderRecurRearchiveProcess(treeQueue: &treeQueue)
    
}


/// 根據(jù)前序隊列進行二叉樹重構
///
/// - Parameter treeQueue: 節(jié)點隊列
/// - Returns: 頭節(jié)點
func preorderRecurRearchiveProcess(treeQueue : inout [String]) -> TreeNode? {
    let value = treeQueue.removeFirst()
    if value == "#" { //頭節(jié)點為空
        return nil
    }
    
    let root = TreeNode.init(_val: Int(value)!) //設置根節(jié)點
    root.left = preorderRecurRearchiveProcess(treeQueue: &treeQueue) //設置左節(jié)點
    root.right = preorderRecurRearchiveProcess(treeQueue: &treeQueue) //設置右節(jié)點
    
    return root
}

非遞歸

與遍歷時不同耿战，我們無法通過節(jié)點是否為nil判斷該構建哪一個子節(jié)點蛋叼。

所以我們需要引入一個變量setleft來確定下一次需要構建的節(jié)點方向。

需要注意的是：

每次構建新節(jié)點之后剂陡，下一次都會嘗試構建其左側節(jié)點狈涮。
而每次遇到空節(jié)點后，都會將頂元素推出鸭栖，并嘗試構建其的右側節(jié)點歌馍。

/// 前序遍歷解歸檔
///
/// - Parameter str: 歸檔字符串
/// - Returns: 頭節(jié)點
func preorderRearchive(str: String?) -> TreeNode? {
    var treeQueue = (str?.components(separatedBy: "!"))!
    treeQueue.removeLast() //這里切割完畢之后最后數(shù)組的最后一位為""

    var stack = [TreeNode]() //遍歷用的棧
    var node : TreeNode //當前操作的節(jié)點
    
    if treeQueue.isEmpty || treeQueue.first == "#" { //頭節(jié)點為空
        return nil
    }

    let root = TreeNode.init(_val: Int(treeQueue.removeFirst())!) //設置root節(jié)點
    node = root//將頭節(jié)點記錄為當前操作的節(jié)點
    stack.append(root) //將頭節(jié)點記錄
    var setleft = true //記錄當前需要構建的節(jié)點方向
    
    while !treeQueue.isEmpty {
        let value = treeQueue.removeFirst() //將隊列首元素推出
        if value != "#" { //若當前節(jié)點不為空
            let newNode = TreeNode.init(_val: Int(value)!) //獲得新的節(jié)點
            //與當前節(jié)點相連
            if setleft {
                node.left = newNode
            }else {
                node.right = newNode
            }
            node = newNode //記錄當前節(jié)點
            stack.append(node) //記錄當前層級
            setleft = true //下一次，嘗試構建左節(jié)點
            
        }else {
            if treeQueue.isEmpty {
                return root //如果已經(jīng)遍歷完成
            }else {
                node = stack.removeLast() //嘗試構建上層
            }
            setleft = false //下一次晕鹊，嘗試構建右節(jié)點
        }
    }

    return root //返回頭節(jié)點
}

廣度遍歷歸檔&&解歸檔

廣度遍歷的歸檔&&解歸檔比深度遍歷容易理解的多松却。

因為他的隊列，只負責記錄下一次想要處理的節(jié)點溅话。
并不需要在意左右與層級倒退晓锻，只需要處理節(jié)點為空的情況即可。

歸檔

/// 廣度遍歷歸檔
///
/// - Parameter root: 頭節(jié)點
/// - Returns: 歸檔字符串
func BFSArchive(root: TreeNode?) -> String {
    
    if root == nil {
        return ""
    }
    
    var res = ""
    var queue = [TreeNode]()
    queue.append(root!)
    
    res += root!.val.description + "!"
    
    while !queue.isEmpty {
        let node = queue.removeFirst() //將當前節(jié)點出隊
        
        if node.left != nil { //嘗試將左節(jié)點入隊
            queue.append(node.left!)
            
            res += node.left!.val.description + "!" //打印當前節(jié)點
        }else {
            res += "#!" //打印當前節(jié)點
        }
        
        if node.right != nil { //嘗試將右節(jié)點入隊
            queue.append(node.right!)
            res += node.right!.val.description + "!" //打印當前節(jié)點
        }else {
            res += "#!" //打印當前節(jié)點
        }
    }
    
    return res
}

解歸檔

/// 廣度遍歷解歸檔
///
/// - Parameter str: 歸檔字符串
/// - Returns: 頭節(jié)點
func BFSRearchive(str: String?) -> TreeNode?{
    
    var treeQueue = (str?.components(separatedBy: "!"))!
    var i = 0
    treeQueue.removeLast() //這里切割完畢之后最后數(shù)組的最后一位為""
    
    var queue = [TreeNode]()

    if treeQueue.isEmpty || treeQueue.first == "#" { //頭節(jié)點為空
        return nil
    }
    
    let root = TreeNode.init(_val: Int(treeQueue[i])!) //設置root節(jié)點
    i+=1
    queue.append(root)
    
    while !queue.isEmpty && i<treeQueue.count{
        let node = queue.removeFirst() //將當前節(jié)點出隊
        if treeQueue[i] != "#" { //嘗試構建左節(jié)點
            node.left = TreeNode.init(_val: Int(treeQueue[i])!)
        }
        i+=1
        if treeQueue[i] != "#" { //嘗試構建右節(jié)點
            node.right = TreeNode.init(_val: Int(treeQueue[i])!)
        }
        i+=1
        
        if node.left != nil { //嘗試將左節(jié)點入隊
            queue.append(node.left!)
        }
        if node.right != nil { //嘗試將右節(jié)點入隊
            queue.append(node.right!)
        }

    }
    return root
}

二叉樹的子樹

在二叉樹中以任何一個節(jié)點為頭部飞几，其下方的整棵樹作為二叉樹的子樹带射。

子樹

非子樹

平衡二叉樹(AVL樹)

空樹為平衡二叉樹

不為空的二叉樹。其中所有的子樹循狰，左右兩側高度差不超過1窟社。

如下圖中第三棵二叉樹券勺。
2節(jié)點的子樹下方，左側高度為2灿里，右側高度為0关炼。所以不是一個平衡二叉樹。

判斷是否為平衡二叉樹

通過遞歸的方式判斷每個子樹是否為AVL樹

一旦一側子節(jié)點為空匣吊，另一側若高度大于2儒拂，則判定為否

/// 是否為平衡二叉樹
///
/// - Parameter root: 子樹頭節(jié)點
/// - Returns: 子樹是否平衡
func isBalance(root : TreeNode?) -> Bool {
    if root == nil { //空樹為AVL樹
        return true
    }
    
    let left = root?.left
    let right = root?.right
    if ((left?.left != nil) || (left?.right != nil)) && right == nil{
        return false  //左側比右側高2
    }
    if ((right?.left != nil) || (right?.right != nil)) && left == nil{
        return false  //右側比左側高2
    }
    
    //否則繼續(xù)判定子樹
    if isBalance(root: left) && isBalance(root: right) {
        return true
    }else {
        return false
    }
}

搜索二叉樹

又叫二叉查找樹，二叉排序樹
特征為色鸳，每個子樹的頭節(jié)點>左節(jié)點社痛，并且頭節(jié)點<右節(jié)點

二叉樹的中序排列，一定是一個有序數(shù)組命雀。反之亦然

紅黑樹蒜哀，平衡搜索二叉樹(平衡AVL樹)等，都是搜索二叉樹的不同實現(xiàn)吏砂。

目的都是提高搜索二叉樹的效率撵儿，調(diào)整代價降低。

判斷一個二叉樹是否為搜索二叉樹

在中序遍歷中狐血，如果上次的值小于當前的值淀歇，則證否

/// 判斷一個二叉樹樹否為搜索二叉樹
///
/// - Parameter root: 根節(jié)點
/// - Returns: 結果
func isBST(root: TreeNode?) -> Bool {

    var stack = [TreeNode]()
    var node = root
    
    var lastValue = -NSIntegerMax
    
    while !stack.isEmpty || node != nil {
        if node != nil {
            stack.append(node!) //將當前節(jié)點依次入棧
            node = node!.left //嘗試遍歷左節(jié)點
        } else {

            let parentsNode = stack.removeLast() //取出當前節(jié)點的父節(jié)點

            if lastValue > parentsNode.val {
                return false
            }
            lastValue = parentsNode.val
            node = parentsNode.right //嘗試遍歷右節(jié)點
        }
    }
    
    return true
}

復原一個交換了位置的搜索二叉樹

搜索二叉樹本身的中序遍歷是升序排序。一旦有兩節(jié)點交換了位置匈织，就一定有一到兩個部分產(chǎn)生降序浪默。

#1. 遍歷中出現(xiàn)了兩次局部降序

#1,2,3,4,5

#1,5,3,4,2

第一個錯誤的節(jié)點為第一次降序較大的節(jié)點
第二個錯誤的節(jié)點為第二次降序較小的節(jié)點

#2. 遍歷中只出現(xiàn)了一次局部降序

#1,2,3,4,5

#1,2,4,3,5

第一個錯誤的節(jié)點為此次降序較大的節(jié)點
第二個錯誤的節(jié)點為此次降序較小的節(jié)點

滿二叉樹

對于國內(nèi)的滿二叉樹

除最后一層無任何子節(jié)點外，每一層上的所有結點都有兩個子結點二叉樹缀匕。

從圖形形態(tài)上看纳决，滿二叉樹外觀上是一個三角形

國內(nèi)的滿二叉樹屬于完全二叉樹

這種滿二叉樹的層數(shù)為L，節(jié)點數(shù)為N弦追。
則N = 2^L-1 ,L = log(N+1)

對于國外的滿二叉樹

滿二叉樹的結點要么是葉子結點岳链，度為0花竞，要么是度為2的結點劲件，不存在度為1的結點。

完全二叉樹

在滿二叉樹的基礎上约急，最后一層所有的結點都連續(xù)集中在最左邊零远，這就是完全二叉樹。

判斷完全二叉樹

通過寬度遍歷的方式進行厌蔽。

計算完全二叉樹的節(jié)點個數(shù)牵辣，要求復雜度小于O(N)

完全二叉樹的左右子樹，一定有一邊是滿二叉樹（左側高度H奴饮，右側高度H-1）纬向。

先遍歷左子樹左邊界择浊，再遍歷右子樹左邊界。從而判斷哪邊為滿二叉樹逾条。
滿二叉樹側琢岩，N=2^H。非滿二叉樹側权埠，遞歸澳腹。

//完全二叉樹節(jié)點個數(shù)
func nodeNum(root: TreeNode?) -> Int {
    if root == nil {
        return 0
    }
    return bs(node: root!, level: 1, h: mostLeftLeve(node: root, level: 1))
}



/// 以node為頭的所有節(jié)點個數(shù)
///
/// - Parameters:
///   - node: 當前節(jié)點
///   - level: 當前節(jié)點層數(shù)
///   - h: 總深度
/// - Returns: 節(jié)點個數(shù)
func bs(node: TreeNode,level: Int ,h: Int) -> Int {
    if level == h {
        return 1
    }
    
    //比較節(jié)點右子樹深度與當前樹深度
    if mostLeftLeve(node: node.right, level: level+1) == h {
        //左樹已滿替蛉。2^(h-level)+右樹節(jié)點數(shù)
        return 1<<(h-level) + bs(node: node.right!, level: level+1, h: h)
    }else {
        //右樹已滿。2^(h-level-1)+左樹節(jié)點數(shù)
        return 1<<(h-level-1) + bs(node: node.left!, level: level+1, h: h)
    }
}


/// 獲取當前子樹總高度
///
/// - Parameters:
///   - node: 頭節(jié)點
///   - level: 當前層級
/// - Returns: 左邊界總高度
func mostLeftLeve(node: TreeNode?,level: Int) -> Int {
    var node = node
    var level = level
    while node != nil {
        node = node!.left!
        level+=1
    }
    return level-1
}

每層只遍歷一個節(jié)點的子樹糕篇，總計LogN。
每個子樹獲取右子樹左邊界遍酌心，需要經(jīng)歷LogN次計算拌消。
總復雜度O((LogN^2))

數(shù)組與完全二叉樹

如果從下標從1開始存儲，則編號為i的結點的主要關系為：
雙親：下取整（i/2）
左孩子：2i
右孩子：2i+1

如果從下標從0開始存儲谒府，則編號為i的結點的主要關系為：
雙親：下取整（(i-1)/2）
左孩子：2i+1
右孩子：2i+2

#這個規(guī)律拼坎，通常用來對通過指定下標取得相關節(jié)點下標。

后序節(jié)點與前驅(qū)節(jié)點

中序遍歷中的下一個遍歷點與上一個遍歷點

2的后序節(jié)點為3完疫，2的前驅(qū)節(jié)點為1

二叉樹中兩節(jié)點間的距離

可以向上或向下走泰鸡，但每個節(jié)點只能經(jīng)過一次。

下圖中2壳鹤，1兩節(jié)點距離為2盛龄。3，5節(jié)點距離為5

最大距離只有三種情況

head左子樹上的最大距離
head右子樹上的最大距離
head左子樹上離head左孩子最遠的距離芳誓，加上head自身節(jié)點余舶，再加上head右子樹上離head右孩子最遠的距離。也就是兩個節(jié)點分別來自不同子樹的情況锹淌。

三個情況下最大的結果匿值，就是以head為頭節(jié)點的整棵樹上最遠的距離。

參考資料

Swift 算法實戰(zhàn)之路：二叉樹
 左神牛課網(wǎng)算法課

數(shù)據(jù)結構基礎--二叉樹

本文主要作為自己的學習筆記官份，并不具備過多的指導意義妹萨。

目錄

基本概念

基本結構

二叉樹的重點

能夠結合隊列艇潭，棧回还，鏈表裆泳，字符串等很多數(shù)據(jù)結構出題。

基本遍歷方式：比如BFS（廣度）柠硕，DFS（深度）工禾。

遞歸的使用

二叉樹的遍歷

先序遍歷

中序遍歷

后續(xù)遍歷

實現(xiàn)先序遍歷

遞歸

非遞歸

還有一種方式

實現(xiàn)中序遍歷

遞歸

非遞歸

先序遍歷與中序遍歷的非遞歸實現(xiàn)都是嘗試分解左邊界的過程

實現(xiàn)后序遍歷

遞歸

非遞歸

另一種非遞歸

以每層換行的方式進行廣度遍歷

具體操作上

代碼實現(xiàn)

二叉樹的序列化和反序列化

序列化方式

一棵樹序列化的結果和反序列化生成的二叉樹都是唯一的

序列化和遍歷二叉樹的區(qū)別

反序列化

前序遍歷的歸檔&&解歸檔

歸檔

解歸檔

遞歸

非遞歸

需要注意的是：

廣度遍歷歸檔&&解歸檔

歸檔

解歸檔

二叉樹的子樹

子樹

非子樹

平衡二叉樹(AVL樹)

判斷是否為平衡二叉樹

搜索二叉樹

二叉樹的中序排列，一定是一個有序數(shù)組命雀。反之亦然

紅黑樹蒜哀，平衡搜索二叉樹(平衡AVL樹)等，都是搜索二叉樹的不同實現(xiàn)吏砂。

判斷一個二叉樹是否為搜索二叉樹

復原一個交換了位置的搜索二叉樹

#1. 遍歷中出現(xiàn)了兩次局部降序

#1,2,3,4,5

#1,5,3,4,2

#2. 遍歷中只出現(xiàn)了一次局部降序

#1,2,3,4,5

#1,2,4,3,5

滿二叉樹

對于國內(nèi)的滿二叉樹

國內(nèi)的滿二叉樹屬于完全二叉樹

對于國外的滿二叉樹

完全二叉樹

判斷完全二叉樹

計算完全二叉樹的節(jié)點個數(shù)牵辣，要求復雜度小于O(N)

數(shù)組與完全二叉樹

#這個規(guī)律拼坎，通常用來對通過指定下標取得相關節(jié)點下標。

后序節(jié)點與前驅(qū)節(jié)點

二叉樹中兩節(jié)點間的距離

最大距離只有三種情況

參考資料