詳解面試中樹的三種遍歷方式！？
在大廠面試中算法也是扮演了越來越重要的角色，從剛開始鏈表數組問題，一步步捲到了樹和動態規劃。最近也有一些小夥伴私信有沒有數據結構算法相關資料，說起來 Go 相關的數據結構與算法的資料真的很少，而且寫的比較好的資料一般用的也是 C/C++，因此小老虎決定以後有空也會繼續跟進數據結構與算法相關的文章。這篇就從常見的樹開始，樹也是工作中很常見的數據結構，學好樹對我們日常分析優化程序也大有毗益。
什麼是二叉樹
我們會常常聽到大佬們談紅黑樹、二叉平衡樹、B 樹、B + 樹。那麼最基本的樹是什麼呢？在計算機中滿足下面 4 個特點的數據結構就可以被稱爲樹了
-
每個節點都只有有限個子節點或無子節點；
-
一個非根節點有且只有一個父節點；
-
除了根節點外，每個子節點可以分爲多個不相交的子樹；
-
樹裏面沒有環路 (cycle)
常見的二叉樹定義即在樹的基礎上再加上一個每個節點最多隻有兩個分支的限制。
二叉樹的遍歷
遞歸遍歷
問題：
分析：求後序遍歷，在未規定時間複雜度和空間複雜度的情況下，最簡單的做法就是遞歸遍歷。遞歸概念很簡單，函數的定義中調用函數自身。其實也就是循環調用，從根節點出發遍歷左右子樹，當一個節點的左右子樹都遍歷完時，將該節點的 value 放入返回的切片中，這樣依次循環下去，只不過是編譯器負責壓棧，不需要你用for調用。
代碼：
1//樹的節點
2type TreeNode struct {
3 Val int
4 Left *TreeNode
5 Right *TreeNode
6}
7
8//遞歸遍歷(便於講解這裏將nums定義在返回值中)
9func preorderTraversal(root *TreeNode) (nums []int) {
10 if root == nil {
11 return nil
12 }
13
14 //前序
15 //nums = append(nums, root.Val)
16 preorderTraversal(root.Left)
17
18 //中序
19 //nums = append(nums, root.Val)
20 preorderTraversal(root.Right)
21
22 //後續
23 ums = append(nums, root.Val)
24 return nums
25}非遞歸遍歷
分析：上面說了遞歸調用的實現，下面來試試如果不借助編譯器壓棧，自己通過棧模擬編譯器的壓棧該怎麼做！（面試中常問的也是非遞歸調用）實現方法仍從後序遍歷的定義出發，優先遍歷根節點的左子樹，當左子樹遍歷結束時再遍歷右子樹，當左右都遍歷結束時，打印根節點值。那麼從根節點出發遍歷左右子樹會有三種情況
情況 1：左子樹不爲空（或未遍歷）
情況 2：左子樹已遍歷結束右子樹未遍歷
情況 3：左右子樹都遍歷結束
下面是本題後序非遞歸的流程圖
代碼實現：
1//樹的節點
2type TreeNode struct {
3 Val int
4 Left *TreeNode
5 Right *TreeNode
6}
7
8//自定義節點
9type Node struct {
10 treeNode *TreeNode
11 flag bool //用於標識該節點的左子樹是否遍歷結束
12}
13
14func postorderTraversal(root *TreeNode) []int {
15 if root == nil {
16 return nil
17 }
18 //存放後序遍歷結果
19 res := make([]int, 0)
20 //模擬棧
21 s := make([]Node, 0)
22 //建立自定義頭節點
23 node := Node{}
24 node.flag = false
25 node.treeNode = root
26 //將頭節點放入棧中
27 s = append(s, node)
28
29 //棧不爲空則循環調用棧中的節點
30 for len(s) != 0 {
31 //優先遍歷左孩子並放入棧中
32 for node.treeNode.Left != nil && !node.flag {
33 //將左孩子放入棧中
34 node = Node{
35 treeNode: node.treeNode.Left,
36 flag: false,
37 }
38 s = append(s, node)
39 }
40
41 //左孩子爲空，表示左子樹爲空
42 //因此將棧頂的一個節點標誌爲設爲true
43 s[len(s)-1].flag = true
44
45 //右孩子不爲空將當前節點設爲右孩子
46 if node.treeNode.Right != nil {
47 node=Node{
48 treeNode: node.treeNode.Right,
49 flag: false,
50 }
51 s = append(s, node)
52 //回到循環開始，遍歷右孩子的左子樹
53 continue
54 }
55
56 //如果左孩子與右孩子都遍歷結束
57 for node.flag {
58 //將節點值放入返回切片中
59 res = append(res, node.treeNode.Val)
60 //將該節點從棧上彈出
61 s = s[:len(s)-1]
62 if len(s) == 0 {
63 break
64 }
65 //將當前節點設爲棧頂元素
66 node = s[len(s)-1]
67 }
68 //進行彈棧後的棧頂元素節點左子樹遍歷結束
69 node.flag = true
70 }
71 return res
72}層次遍歷
問題：
分析：
層次遍歷其實也就是廣度優先搜索，將根節點放入根節點隊列cur中，再從根節點層所在的隊列cur出發，將根節點所能遍歷到的孩子節點放入下層節點隊列next中。根節點層遍歷結束時，將根節點層cur替換下層節點隊列next，這樣依次遞推下去，直到樹中所有節點都被遍歷一遍。
代碼：
1func levelOrder(root *TreeNode) [][]int {
2 //存放遍歷結果的切片
3 res := [][]int{}
4 //檢查根節點
5 if root == nil {
6 return res
7 }
8 //存放當前遍歷層根節點的隊列
9 cur := []*TreeNode{root}
10
11 //循環遍歷cur中所有節點
12 for i := 0; len(cur) > 0; i++ {
13 res = append(res, []int{})
14 next := []*TreeNode{}
15
16 //循環遍歷根節點層節點
17 for j := 0; j < len(cur); j++ {
18 node := cur[j]
19 res[i] = append(res[i], node.Val)
20 //遍歷根節點的左右孩子放入到下層待遍歷到節點中
21 if node.Left != nil {
22 next = append(next, node.Left)
23 }
24 if node.Right != nil {
25 next = append(next, node.Right)
26 }
27 }
28
29 //一層節點遍歷結束將cur替換爲下層節點
30 cur = next
31 }
32 return res
33}總結
本文敘述了樹的定義的四個限制條件，以及樹的遞歸、非遞歸、按層三種樹的遍歷方式。遞歸調用的本質是編譯器幫忙壓棧的循環調用，非遞歸調用需要利用標誌位搭配棧模擬節點出入棧，按層遍歷需要利用倆個隊列，一層節點放在一個隊列，一層一層迭代下去。雖然不是很難，但是非遞歸遍歷和按層遍歷也是面試的常考點，遞歸遍歷雖然不直接考，但是在此基礎上有很多變式題目，更是後面樹相關算法的基礎，希望小夥伴們能動手多敲幾遍！爲後面介紹樹的更多變式算法打好基礎！
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/aX4W3X7B1c7bic9K2T9j2A