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

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


那么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
}

大概解释一下这一段代码:

  1. 要比较val的值,必须实现了判断相等的协议Equatable
  2. 返回值是[T]?,而不是[T],实际上空数组也可以表示为没有找到,这里考虑在实现的时候要判断左右子树返回的是否为空,用nil比较容易判断,可以比较方便使用if let??操作符
  3. 参数是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语法。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 220,884评论 6 513
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 94,212评论 3 395
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 167,351评论 0 360
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 59,412评论 1 294
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 68,438评论 6 397
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 52,127评论 1 308
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,714评论 3 420
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,636评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 46,173评论 1 319
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 38,264评论 3 339
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,402评论 1 352
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 36,073评论 5 347
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,763评论 3 332
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,253评论 0 23
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,382评论 1 271
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,749评论 3 375
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 45,403评论 2 358

推荐阅读更多精彩内容