题目：在一个二叉树中（假定没有重复元素），查找指定元素，输出从根节点到该元素路径上的所有节点的值
例子：假设有一个二叉树如下：
那么5的路径为
[2, 7, 6, 5]，4的路径为[2, 5, 9, 4]
问题分析
由于题目给出的二叉树并没有排序，要找出对应节点必须要对整个树进行遍历，直到找到目标节点为止，可以采取后序深度优先遍历，这样的好处在于深度优先遍历当查找到对应的节点时，当前保存在栈里的路径刚好是问题需要的路径。
数据结构定义
首先给出一个基本的数据结构定义
class Tree<T> {
var left: Tree<T>? //为nil时表示没有左子树
var right: Tree<T>? //为nil时表示没有右子树
let value: T
init(_ val: T) {
value = val
}
}
在这个定义中使用了Optional类型的数据来区分一个节点是否包含左右子树，整体比较简单
递归解法
一般的二叉树的数据结构，都可以优先考虑使用递归来解决问题，递归本身也是处理这种问题比较自然的思路，并且非常简洁，在这个题目里面使用递归的思路来描述解题思路用状态来描述就是：
使用代码来实现就是：
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的值，必须实现了判断相等的协议
Equatable - 返回值是
[T]?，而不是[T]，实际上空数组也可以表示为没有找到，这里考虑在实现的时候要判断左右子树返回的是否为空，用nil比较容易判断，可以比较方便使用if let和??操作符 - 参数是
Tree<T>?而不是Tree<T>，这里也考虑的是递归调用的时候不需要判断左右子树是否为空
当然代码也可以像下面这样，没有太大区别，看个人习惯就好
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 [ ]
}
非递归解法
为什么要有非递归解法，确实，有了递归之后已经很方便了，但是非递归解法也有一些可取之处，这里不对递归和非递归优缺点进行讨论。
使用非递归对二叉树进行深度优先遍历本身需要stack的支持，如果只是遍历的话，有前中后三种顺序进行输出，不过我们要保存最后访问元素和根节点之间的节点，不能多也不能少，刚好和后序遍历的堆栈结构比较接近，所以根据后序遍历的解法进行修改：
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 {
//找到目标，返回路径对应的值
return stk.map { $0.value}
}
//if top为叶子结点或者左右节点都访问过了，top出栈
//else top的左节点访问过了，那么下一步访问右节点
//其它情况访问左节点
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!]
}
}
//没找到目标，返回空数组
return [ ]
}
这个遍历还有一种优化写法，就是每次往栈中push节点的时候，一次性把这个节点的左子树循环压栈，这么修改一下算法稍微有一些区别，就是在判断的地方要记得左子树已经入栈了不用再判断了，修改后的代码如下：
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 []
}
递归数据结构
在函数式编程语言中最常见的就是归纳型数据，其实就是递归的数据结构，前面的数据结构中Tree里面包含Tree，其实就是一种归纳性质了，swift中还有另外一种另外一种数据结构的定义方法，更接近与函数式编程语言里面的概念，配合模式匹配使用，也是一种非常强大的功能。
indirect enum 数据结构定义
indirect enum BTree<T> {
case Empty
case Node(T, BTree<T>, BTree<T>)
}
定义中indirect表示这个数据结构可以递归使用，没有这个关键词就会报错啦。
对于定义的两个case，一个表示空二叉树，一个表示节点，节点由一个值和左右子树构成，整体和前面的结构并没有太大区别，下面看看在实现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
}
这里在算法上和前面的递归算法并没有区别，十分的简单，使用enum的算法看起来更加清晰一些。
测试代码
//从BTree到Tree的转换
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
总结
递归的解法会比较优雅，简洁，一般情况下考虑递归方式。
这个算法题目本身比较简单，更多的是学习一些swift语法。
网友评论