題目：在一個(gè)二叉樹中（假定沒有重復(fù)元素），查找指定元素，輸出從根節(jié)點(diǎn)到該元素路徑上的所有節(jié)點(diǎn)的值
例子：假設(shè)有一個(gè)二叉樹如下：
那么5的路徑為
[2, 7, 6, 5]，4的路徑為[2, 5, 9, 4]
問題分析
由于題目給出的二叉樹并沒有排序，要找出對(duì)應(yīng)節(jié)點(diǎn)必須要對(duì)整個(gè)樹進(jìn)行遍歷，直到找到目標(biāo)節(jié)點(diǎn)為止，可以采取后序深度優(yōu)先遍歷，這樣的好處在于深度優(yōu)先遍歷當(dāng)查找到對(duì)應(yīng)的節(jié)點(diǎn)時(shí)，當(dāng)前保存在棧里的路徑剛好是問題需要的路徑。
數(shù)據(jù)結(jié)構(gòu)定義
首先給出一個(gè)基本的數(shù)據(jù)結(jié)構(gòu)定義
class Tree<T> {
var left: Tree<T>? //為nil時(shí)表示沒有左子樹
var right: Tree<T>? //為nil時(shí)表示沒有右子樹
let value: T
init(_ val: T) {
value = val
}
}
在這個(gè)定義中使用了Optional類型的數(shù)據(jù)來區(qū)分一個(gè)節(jié)點(diǎn)是否包含左右子樹，整體比較簡(jiǎn)單
遞歸解法
一般的二叉樹的數(shù)據(jù)結(jié)構(gòu)，都可以優(yōu)先考慮使用遞歸來解決問題，遞歸本身也是處理這種問題比較自然的思路，并且非常簡(jiǎn)潔，在這個(gè)題目里面使用遞歸的思路來描述解題思路用狀態(tài)來描述就是：
使用代碼來實(shí)現(xiàn)就是：
func find_path1<T: Equatable>(_ root: Tree<T>?, _ val: T) -> [T]? {
guard let root = root else {
return nil
}
if val == root.value {
return [val]
}
//這里把左右子樹的查找合并在一起，減少一些代碼，邏輯和上面分析的是一致的
if let path = find_path1(root.left, val) ?? find_path1(root.right, val) {
return [root.value] + path
}
return nil
}
大概解釋一下這一段代碼：
- 要比較val的值，必須實(shí)現(xiàn)了判斷相等的協(xié)議
Equatable - 返回值是
[T]?，而不是[T]，實(shí)際上空數(shù)組也可以表示為沒有找到，這里考慮在實(shí)現(xiàn)的時(shí)候要判斷左右子樹返回的是否為空，用nil比較容易判斷，可以比較方便使用if let和??操作符 - 參數(shù)是
Tree<T>?而不是Tree<T>，這里也考慮的是遞歸調(diào)用的時(shí)候不需要判斷左右子樹是否為空
當(dāng)然代碼也可以像下面這樣，沒有太大區(qū)別，看個(gè)人習(xí)慣就好
func find_path2<T: Equatable>(_ root: Tree<T>, _ val: T) -> [T] {
if val == root.value {
return [val]
}
if let left = root.left {
let path = find_path2(left, val)
if !path.isEmpty {
return [root.value] + path
}
}
if let right = root.right {
let path = find_path2(right, val)
if !path.isEmpty {
return [root.value] + path
}
}
return [ ]
}
非遞歸解法
為什么要有非遞歸解法，確實(shí)，有了遞歸之后已經(jīng)很方便了，但是非遞歸解法也有一些可取之處，這里不對(duì)遞歸和非遞歸優(yōu)缺點(diǎn)進(jìn)行討論。
使用非遞歸對(duì)二叉樹進(jìn)行深度優(yōu)先遍歷本身需要stack的支持，如果只是遍歷的話，有前中后三種順序進(jìn)行輸出，不過我們要保存最后訪問元素和根節(jié)點(diǎn)之間的節(jié)點(diǎn)，不能多也不能少，剛好和后序遍歷的堆棧結(jié)構(gòu)比較接近，所以根據(jù)后序遍歷的解法進(jìn)行修改：
func find_path3<T: Equatable>(_ root: Tree<T>, _ val: T) -> [T] {
var prev = root
var stk = [root]
while !stk.isEmpty {
let top = stk.last!
if top.value == val {
//找到目標(biāo)，返回路徑對(duì)應(yīng)的值
return stk.map { $0.value}
}
//if top為葉子結(jié)點(diǎn)或者左右節(jié)點(diǎn)都訪問過了，top出棧
//else top的左節(jié)點(diǎn)訪問過了，那么下一步訪問右節(jié)點(diǎn)
//其它情況訪問左節(jié)點(diǎn)
if (top.left == nil && top.right == nil) ||
prev === top.right ?? top.left {
prev = stk.popLast()!
} else if prev === top.left || top.left == nil {
stk += [top.right!]
} else {
stk += [top.left!]
}
}
//沒找到目標(biāo)，返回空數(shù)組
return [ ]
}
這個(gè)遍歷還有一種優(yōu)化寫法，就是每次往棧中push節(jié)點(diǎn)的時(shí)候，一次性把這個(gè)節(jié)點(diǎn)的左子樹循環(huán)壓棧，這么修改一下算法稍微有一些區(qū)別，就是在判斷的地方要記得左子樹已經(jīng)入棧了不用再判斷了，修改后的代碼如下：
func push_all_left<T>(_ node: Tree<T>) -> [Tree<T>] {
var top : Tree<T>? = node
var stk: [Tree<T>] = []
while top != nil {
stk += [top!]
top = top?.left
}
return stk
}
func find_path4<T: Equatable>(_ root: Tree<T>, _ val: T) -> [T] {
var prev = root
var stk = push_all_left(root)
while !stk.isEmpty {
let top = stk.last!
if top.value == val {
return stk.map { $0.value}
}
if top.right == nil || prev === top.right {
prev = stk.popLast()!
} else {
stk += push_all_left(top.right!)
}
}
return []
}
遞歸數(shù)據(jù)結(jié)構(gòu)
在函數(shù)式編程語言中最常見的就是歸納型數(shù)據(jù)，其實(shí)就是遞歸的數(shù)據(jù)結(jié)構(gòu)，前面的數(shù)據(jù)結(jié)構(gòu)中Tree里面包含Tree，其實(shí)就是一種歸納性質(zhì)了，swift中還有另外一種另外一種數(shù)據(jù)結(jié)構(gòu)的定義方法，更接近與函數(shù)式編程語言里面的概念，配合模式匹配使用，也是一種非常強(qiáng)大的功能。
indirect enum 數(shù)據(jù)結(jié)構(gòu)定義
indirect enum BTree<T> {
case Empty
case Node(T, BTree<T>, BTree<T>)
}
定義中indirect表示這個(gè)數(shù)據(jù)結(jié)構(gòu)可以遞歸使用，沒有這個(gè)關(guān)鍵詞就會(huì)報(bào)錯(cuò)啦。
對(duì)于定義的兩個(gè)case，一個(gè)表示空二叉樹，一個(gè)表示節(jié)點(diǎn)，節(jié)點(diǎn)由一個(gè)值和左右子樹構(gòu)成，整體和前面的結(jié)構(gòu)并沒有太大區(qū)別，下面看看在實(shí)現(xiàn)find_path算法上有什么樣的不同：
func find_path5<T: Equatable>(_ tree: BTree<T>, _ val: T) -> [T]? {
switch tree {
case .Empty:
return nil
case .Node(val, _, _):
return [val]
case .Node(let value, let left, let right):
if let path = find_path5(left, val) ?? find_path5(right, val) {
return [value] + path
}
}
return nil
}
這里在算法上和前面的遞歸算法并沒有區(qū)別，十分的簡(jiǎn)單，使用enum的算法看起來更加清晰一些。
測(cè)試代碼
//從BTree到Tree的轉(zhuǎn)換
func convert<T>(tree: BTree<T>) -> Tree<T>? {
switch tree {
case .Empty:
return nil
case .Node(let root, let left, let right):
let t = Tree(root)
t.left = convert(tree: left)
t.right = convert(tree: right)
return t
}
}
//開頭提到的那棵樹
let test = BTree.Node(2, .Node(7, .Node(2, .Empty, .Empty), .Node(6, .Node(5, .Empty, .Empty), .Node(11, .Empty, .Empty))), .Node(5, .Empty, .Node(9, .Node(4, .Empty, .Empty), .Empty)))
let test1 = convert(tree: test)!
let val = 4
let p1 = find_path1(test1, val)
let p2 = find_path2(test1, val)
let p3 = find_path3(test1, val)
let p4 = find_path4(test1, val)
let p5 = find_path5(test, val)
代碼還在這里：https://repl.it/@lency/path-for-tree
總結(jié)
遞歸的解法會(huì)比較優(yōu)雅，簡(jiǎn)潔，一般情況下考慮遞歸方式。
這個(gè)算法題目本身比較簡(jiǎn)單，更多的是學(xué)習(xí)一些swift語法。
