點(diǎn)贊關(guān)注绞惦，不再迷路肤晓，你的支持對我意義重大氛雪！

?? Hi，我是丑丑卦尊。本文「數(shù)據(jù)結(jié)構(gòu) & 算法」| 導(dǎo)讀 —— 登高博見 已收錄，這里有 Android 進(jìn)階成長路線筆記 & 博客舌厨，歡迎跟著彭丑丑一起成長岂却。（聯(lián)系方式在 GitHub）

目錄

1. 概述

優(yōu)秀的算法往往取決于采用的數(shù)據(jù)結(jié)構(gòu)，在算法面試中裙椭，通常涉及較多的還是幾種基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)躏哩。其中樹（Tree）是最常考的揉燃，也是相對難的扫尺，建議應(yīng)試者優(yōu)先準(zhǔn)備關(guān)于樹的面試題；

1.1 邏輯結(jié)構(gòu)

從邏輯上看炊汤，樹（Tree）是一種非線性結(jié)構(gòu)正驻，樹的節(jié)點(diǎn)包含元素值與所有子節(jié)點(diǎn)的列表。如果按照圖的理論來說抢腐，樹可以看作是一種特殊的圖（N 個(gè)節(jié)點(diǎn)和 N - 1 條邊的連通的有向無環(huán)圖）姑曙；

1.2 存儲結(jié)構(gòu)

從存儲上看，樹可以采用數(shù)組 & 鏈表兩種存儲方式迈倍。鏈表存儲法很直接明了伤靠，就是每個(gè)節(jié)點(diǎn)里都持有子節(jié)點(diǎn)的引用，而數(shù)組存儲法則需要利用下標(biāo)來尋找父子節(jié)點(diǎn)關(guān)系啼染，節(jié)點(diǎn)內(nèi)部不再需要持有子節(jié)點(diǎn)的引用宴合，更加節(jié)約內(nèi)存。

采用數(shù)組存儲方式時(shí)迹鹅，樹的根節(jié)點(diǎn)可以分配在數(shù)組第 [0] 位卦洽，也可以分配在第 [1] 位，兩種方式?jīng)]有明顯的區(qū)別徒欣，主要是計(jì)算子節(jié)點(diǎn) / 父節(jié)點(diǎn)下標(biāo)的公式有所不同：

根節(jié)點(diǎn)存儲在第 [0] 位

2. 對于第 [i] 位上的節(jié)點(diǎn)逐样，第 [2 * i +1] 位是左節(jié)點(diǎn)，第 [2 * i + 2] 位是右節(jié)點(diǎn)
3. 對于第 [i] 位上的節(jié)點(diǎn)打肝，第 [(i-1) / 2] 位是父節(jié)點(diǎn)

根節(jié)點(diǎn)存儲在第 [1] 位

1. 第 [0] 位不存儲脂新，根節(jié)點(diǎn)存儲在第 [1] 位
2. 對于第 [i] 位上的節(jié)點(diǎn)，第 [2 * i] 位是左節(jié)點(diǎn)粗梭，第[2 * i + 1] 位是右節(jié)點(diǎn)
3. 對于第 [i] 位上的節(jié)點(diǎn)争便，第 [i / 2] 位是父節(jié)點(diǎn)

需要注意的是，完全二叉樹采用數(shù)組存儲方式是空間利用率最高的断医。

—— 引用自 https://time.geekbang.org/column/article/67856 王爭 著

2. 樹的遍歷

樹的遍歷是樹最最重點(diǎn)的知識滞乙，也是匙嗉停考的點(diǎn)，因?yàn)樵诮鉀Q其他問題的時(shí)候斩启，通常就需要遍歷整棵樹來尋找答案序调，所以我們必須對 樹的各種遍歷方式 非常熟悉（特別是二叉樹的遍歷）⊥么兀總結(jié)常見的題目发绢，可以將遍歷一棵樹的方式分為：

• 前序遍歷（DFS）
• 中序遍歷（DFS）
• 后序遍歷（DFS）
• 層序遍歷（BFS）
• 路徑遍歷（熱門）
• 垂序遍歷（冷門）

—— 引用自 LeetCode

2.1 前序遍歷 & 中序遍歷 & 后序遍歷

這三種遍歷的區(qū)別：訪問到一個(gè)節(jié)點(diǎn)時(shí)，處理當(dāng)前節(jié)點(diǎn)與處理左右子樹的順序不同垄琐。在前序遍歷中边酒，訪問節(jié)點(diǎn)順序與處理節(jié)點(diǎn)順序是一致的，而另外兩種是不一致的狸窘。

Preorder (root) {
  1. access content of root 
  2. Call Preorder(root.left)
  3. Call Preorder(root.right)
}

Postorder (root) {
  1. Call Postorder(root.left)
  2. Call Postorder(root.right)
  3. access content of root
}

Inorder (root) {
  1. Call Inorder(root.left) 
  2. access content of root
  3. Call Inorder(root.right)
}

• 遞歸解法

遞歸解法可以說很簡單了墩朦，就是調(diào)整左右子樹的遞歸順序即可：

• 非遞歸解法

BFS 的非遞歸解法需要利用棧的 LIFO 特性：

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：

• 空間復(fù)雜度：樹退化鏈表時(shí)最差、樹平衡時(shí)最優(yōu)翻擒，平均

2.2 層序遍歷

層序遍歷需要利用隊(duì)列的 FIFO 特性氓涣，即：每次迭代都將一整層的節(jié)點(diǎn)放進(jìn)隊(duì)列里，如下圖所示：

—— 引用自 https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/bfs-de-shi-yong-chang-jing-zong-jie-ceng-xu-bian-l/ nettee 著

fun levelOrder(root: TreeNode?): List<List<Int>> {
        val result = ArrayList<List<Int>>()

        val queue: Queue<TreeNode> = LinkedList()

        if (null != root) {
            queue.offer(root)
        }

        while (!queue.isEmpty()) {
            val level = ArrayList<Int>()
            // 處理一層
            for (index in 0 until queue.size) {
                val node = queue.poll()
                level.add(node.`val`)
                if (null != node.left) {
                    queue.offer(node.left)
                }
                if (null != node.right) {
                    queue.offer(node.right)
                }
            }
            if (level.isNotEmpty()) {
                result.add(level)
            }
        }
        return result
    }

另外韭寸，層序遍歷也是常見的變型題春哨，例如自底向上、鋸齒形恩伺，其實(shí)無非就是改變輸出結(jié)果的步驟：

- 鋸齒形：

var flag = true

for(...){
    if(flag){
        level.add(node.`val`)
    }else{
        level.addFirst(node.`val`)
    }
}
...
flag = !flag

- 自底向上：

for(...){
    ...
}

result.addFirst(level)

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：
• 空間復(fù)雜度：樹退化鏈表時(shí)最差赴背、樹平衡時(shí)最優(yōu)，平均

2.3 路徑遍歷

路徑遍歷其實(shí)是前面四種遍歷的升級版晶渠，無非就是將經(jīng)過的節(jié)點(diǎn)記錄到String凰荚。下圖的 DFS 解法使用了最簡單的前序遍歷方法：

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：需要復(fù)制字符串，
• 空間復(fù)雜度：樹退化鏈表時(shí)最差褒脯、樹平衡時(shí)最優(yōu)便瑟，平均

2.4 垂序遍歷

Editting...

• 本節(jié)對應(yīng)題目：

  • 987. Vertical Order Traversal of a Binary Tree 二叉樹的垂序遍歷

3. 樹的概念

通常來說不會直接考察樹的相關(guān)概念，但是理解清楚這些概念是解決其他復(fù)雜問題的基礎(chǔ)番川。

—— 引用自 https://time.geekbang.org/column/article/67856 王爭 著

• 路徑：從一個(gè)節(jié)點(diǎn)走到另一個(gè)節(jié)點(diǎn)的經(jīng)過的節(jié)點(diǎn)到涂；
• 距離：通常指最短距離，即兩個(gè)節(jié)點(diǎn)到最近共同祖先的路徑和颁督；
• 高度：從節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑践啄；
• 深度：從節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑；
• 寬度：每層兩個(gè)端點(diǎn)（該層最左和最右的非空節(jié)點(diǎn)沉御，兩端點(diǎn)間的 null 節(jié)點(diǎn)也計(jì)入長度）之間的長度屿讽。

4. 遞歸思想

經(jīng)常地，一棵樹要滿足某種性質(zhì)吠裆，都會要求它的每個(gè)節(jié)點(diǎn)也都滿足該性質(zhì)伐谈，例如對于一棵二叉搜索樹烂完，從它的每棵子樹觀察，都是一棵二叉搜索樹诵棵；或者抠蚣，當(dāng)解一棵樹的最終解時(shí)，一般可先求出左右兩棵子樹的最終解履澳，再結(jié)合當(dāng)前節(jié)點(diǎn)求出最終解柱徙，

通用的解題模板 & 思路如下：

var result = Integer.MIN_VALUE 或 0

fun search(node : TreeNode) : Int{
    1. 左子樹最終解
    val leftResult = search(node.left)

    2. 右子樹最終解
    val rightResult = search(node.right)

    3. 結(jié)合當(dāng)前節(jié)點(diǎn)得出當(dāng)前解
    val bestResult = ...

    4. 更新最優(yōu)解 result

    5. 返回當(dāng)前解
}

例如：求二叉樹的最大深度。要求一棵樹的最大深度奇昙，如果已知左右兩個(gè)子樹的最大深度，那么很明顯這棵樹的最大深度敌完，就是兩棵子樹結(jié)果的最大值再加一储耐。所以這個(gè)問題用遞歸就很輕松可以解決，當(dāng)然是用層序遍歷也能解決：

參考代碼 1
fun maxDepth(root: TreeNode?): Int {
    if (root == null) {
        return 0
    } else {
        val leftHeight = maxDepth(root.left)
        val rightHeight = maxDepth(root.right)
        return Math.max(leftHeight, rightHeight) + 1
    }
}
參考代碼 2
fun maxDepth(root: TreeNode?): Int {
    fun search(root: TreeNode?, parentDepth: Int): Int {
        if (root == null) {
            return parentDepth
        } else {
            val leftHeight = search(root.left, parentDepth + 1)
            val rightHeight = search(root.right, parentDepth + 1)
            return Math.max(leftHeight, rightHeight)
        }
    }
    return search(root, 0)
}

這兩段代碼看起來差不多滨溉，其實(shí)本質(zhì)上是有較大不同的什湘。參考代碼 1 中，+ 運(yùn)算是在子節(jié)點(diǎn)執(zhí)行的晦攒，而參考代碼 2 中闽撤，+ 是在父節(jié)點(diǎn)執(zhí)行的。也就是說脯颜，參考代碼 1 更適合于 “整合子問題的解得到最終解” 的思路哟旗，而參考代碼 2 更適合于 “將父節(jié)點(diǎn)的狀態(tài)傳遞給子節(jié)點(diǎn)”的思路。

5. 路徑問題

前面我們定義了路徑的概念：從一個(gè)節(jié)點(diǎn)走到另一個(gè)節(jié)點(diǎn)的經(jīng)過的節(jié)點(diǎn)栋操，這一節(jié)我們專門討論路徑相關(guān)的問題闸餐。

5.1 向下的路徑（從根到葉子的路徑）

這一類問題找出一條滿足某個(gè)條件的路徑，要求路徑是從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)矾芙。這等于是指明了路徑的起始點(diǎn)和終止點(diǎn)舍沙，因此這類問題只需要按照 第2.3節(jié) - 路徑遍歷 即可輕松解決。

5.2 向下的路徑（非必須從根到葉子的路徑）

這一類問題不要求路徑是從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)剔宪，可以經(jīng)過也可以不經(jīng)過拂铡。因此路徑的起始點(diǎn)和終止點(diǎn)就不確定了，難度會稍稍增大葱绒，那么應(yīng)該怎么解呢感帅？這就要引入 前綴和 的概念。

假設(shè)我們要找和為 10 的路徑哈街，我們可以逐步記錄訪問到節(jié)點(diǎn)的前綴和留瞳，當(dāng)我們訪問到一個(gè)點(diǎn)（記為 B），它的前綴和 - 目標(biāo)和 正好與之前記錄的一個(gè)前綴和相同（記為 A）骚秦，說明從 A 到 B 之間經(jīng)過的路徑和正好就是目標(biāo)和：

5.3 自由路徑

這一類題目不再要求路徑是從上到下的她倘，選擇的可能性更多璧微，例如下圖中經(jīng)過 A 節(jié)點(diǎn)的路徑總共有 4 條：

那么這類問題應(yīng)該怎么解呢？還記得我們說的 遞歸思想嗎硬梁？我們要求這棵樹的最優(yōu)解前硫，假設(shè)我們已求得左右兩顆子樹的解，那么再結(jié)合當(dāng)前節(jié)點(diǎn)求出最終解荧止。例如：124. Binary Tree Maximum Path Sum 二叉樹的最大路徑和

在這道題里屹电，不要求路徑是從上向下的，也不要求結(jié)果一定要經(jīng)過根節(jié)點(diǎn)跃巡，所以是不滿足最優(yōu)子結(jié)構(gòu)的危号。但是我們可以轉(zhuǎn)換一下，先假設(shè)結(jié)果是經(jīng)過根節(jié)點(diǎn)的素邪，使其滿足最優(yōu)子結(jié)構(gòu)：給定一棵樹外莲，假設(shè)已知左子樹和右子樹的最大路徑和，那么對于當(dāng)前樹兔朦，最大路徑和就是兩棵子樹結(jié)果最大值加上根節(jié)點(diǎn)的值偷线。當(dāng)然，根節(jié)點(diǎn)的最大路徑和不一定是整棵樹的最大路徑和沽甥，因此我們需要使用一個(gè)變量記錄錄得的最大值声邦。

6. 祖先問題

6.1 最近共同祖先

6.2 最遠(yuǎn)共同祖先

• 本節(jié)相關(guān)題目：

• 543. Diameter of Binary Tree 二叉樹的直徑

Editting...

5.5 距離

• 863. All Nodes Distance K in Binary Tree 二叉樹中所有距離為 k 的節(jié)點(diǎn)

7. 特殊的樹

前面我們將的樹都是普通的二叉樹，下面討論常見的幾種特殊的二叉樹：

7.1 滿二叉樹

滿二叉樹中摆舟，葉子節(jié)點(diǎn)全部在最底層亥曹，即：除了葉子節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)都擁有左節(jié)點(diǎn)和右節(jié)點(diǎn)恨诱。對于一棵滿二叉樹歇式，從任意一個(gè)子樹看都是滿二叉樹。

編號 2 為滿二叉樹

—— 引用自 https://time.geekbang.org/column/article/67856 王爭 著

7.2 完全二叉樹

完全二叉樹中胡野，葉子節(jié)點(diǎn)都在最后兩層材失，并且最后一層的節(jié)點(diǎn)都靠左排列。對于一棵完全二叉樹硫豆，從任意一個(gè)子樹看都是完全二叉樹龙巨。

—— 引用自 https://time.geekbang.org/column/article/67856 王爭 著

7.3 二叉搜索樹

二叉搜索樹中，對于任意節(jié)點(diǎn)的值來說熊响，都大于左子樹中每個(gè)節(jié)點(diǎn)的值旨别，都小于右子樹中每個(gè)節(jié)點(diǎn)的值。對于一棵二叉搜索樹汗茄，從任意一個(gè)子樹看都是二叉搜索樹秸弛。

—— 引用自 https://time.geekbang.org/column/article/67856 王爭 著

7.4 平衡二叉樹

平衡二叉樹中，對于任意節(jié)點(diǎn)來說，左右子樹的高度差不大于1递览。對于一棵平衡二叉樹叼屠，從任意一個(gè)子樹看都是平衡二叉樹。

平衡二叉樹避免了二叉樹左右子樹高度相差太大是時(shí)間和空間復(fù)雜度退化的問題绞铃。但需要注意的是镜雨，在實(shí)踐中使用的是“近似平衡”，只需要保證左右子樹高度相對平均儿捧，并不需要嚴(yán)格準(zhǔn)守高度差不大于 1 的定義荚坞。

—— 引用自 https://time.geekbang.org/column/article/67856 王爭 著

7.5 平衡二叉搜索樹

平衡二叉搜索樹有很多種，例如伸展樹（Splay Tree）菲盾、樹堆（Treap）颓影、紅黑樹（AVL），其中紅黑樹是最常見的懒鉴。

8. 構(gòu)建二叉樹

• 本節(jié)相關(guān)問題：

從前序和中序遍歷構(gòu)造二叉樹
從中序和后序遍歷構(gòu)造二叉樹
從前序遍歷構(gòu)造二叉樹
從前序和后序遍歷構(gòu)造二叉樹
構(gòu)建高度最小的樹
構(gòu)建二叉搜索樹

Editting...

9. 總結(jié)

• 1. 樹的遍歷解決樹問題的基本編程技巧瞭空，必須熟練掌握遞歸與非遞歸兩種寫法；
• 2. 樹的概念是理解題意的前提疗我，必須保證理解清晰，沒有混淆南捂；
• 3. 遞歸思想非常適用于解決樹問題吴裤，當(dāng)你遇到一個(gè)問題沒有解題思路時(shí)，應(yīng)該先想想：如果你知道左右兩個(gè)子樹（子問題）的答案溺健，是否能清晰的解決當(dāng)前樹的問題麦牺；
• 4. 樹的路徑 & 祖先問題是面試中的常客鞭缭。

參考資料

• 《數(shù)據(jù)結(jié)構(gòu)與算法之美》 —— 王爭 著剖膳，極客時(shí)間 出品
• 《300分鐘搞定算法面試》 —— 力扣&拉勾網(wǎng) 出品
• 《BFS 的使用場景總結(jié)：層序遍歷、最短路徑問題》 —— nettee 著

創(chuàng)作不易岭辣，你的「三連」是丑丑最大的動力吱晒，我們下次見！