算法面试题 - 二叉树 - 节点路径问题 - swift

2019-07-21 本文已影响0人肆_春分

题目：在一个二叉树中（假定没有重复元素），查找指定元素，输出从根节点到该元素路径上的所有节点的值
例子：假设有一个二叉树如下：

那么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类型的数据来区分一个节点是否包含左右子树，整体比较简单

递归解法

一般的二叉树的数据结构，都可以优先考虑使用递归来解决问题，递归本身也是处理这种问题比较自然的思路，并且非常简洁，在这个题目里面使用递归的思路来描述解题思路用状态来描述就是：
$path(root, val) = \left\{ \begin{array}{ll} [val] & \textrm{如果root的值就是val}\\ [val] + path(root.left, val) & \textrm{如果val在左子树}\\ [val] + path(root.right, val) & \textrm{如果val在右子树}\\ nil & \textrm{找不到val}\\ \end{array} \right.$
使用代码来实现就是：

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语法。