cmatrixprobe

发呆业务爱好者

二叉树的递归遍历与recover

前言

defer在Go语言中扮演着重要的角色,极大提高了代码可读性,随着最近两个版本的迭代,其一直被诟病的性能问题也得到大幅提升,不过很多初学者对defer和return的执行顺序不甚了解,下面暂且看一下剑指Offer中的一道题。

题目描述

给定一棵二叉搜索树,请找出其中第k大的节点。

解题思路

二叉搜索树最大的特点是左子树小于根小于右子树,然后递归或者非递归逆中序遍历即可,题目本身没有什么好说的,重点自然不是这个,下图找第3大的节点(值为4)的递归过程。

逆后序遍历

大家都知道,递归写法虽然简单但必须要将整个二叉树全部遍历,当数据量很大而k又很小的时候性能相比非递归写法差距巨大,那么有什么改进的思路呢?
- 首先最简单的想法就是设一个bool值,当遍历到第k个节点时将其置为true,每次遍历前进行判断如果为false才执行,代码如下:

func kthLargest(root *TreeNode, k int) int {
    var res int
    var find bool
    var inOrder func(root *TreeNode)
    inOrder = func(root *TreeNode) {
        if root == nil {
            return
        }
        if !find {
            inOrder(root.Right)
        }
        if !find && k == 1 {
            find = true
            res = root.Val
            return
        }
        k--
        if !find {
            inOrder(root.Left)
        }
    }
    inOrder(root)
    return res
}

不过这样虽然解决了继续向后遍历的问题,但是每次找到目标后还要递归回到根节点,如果目标深度较大,仍然是一个费时的操作。

带flag的逆后续遍历

有没有什么办法能让递归函数在节点4处直接退出呢?按理来说应该是没有的,不过对于Go语言,我想到了panic操作,如果能直接panic,然后用recover接收panic的值再返回问题不就解决了么。


由于recover要搭配defer来使用,这时就要考虑defer的执行顺序了,我一开始是这样写的:

func kthLargest(root *TreeNode, k int) int {
    var res int
    defer func() {
        res = recover().(int)
    }()
    var inOrder func(root *TreeNode)
    inOrder = func(root *TreeNode) {
        if root == nil {
            return
        }
        inOrder(root.Right)
        if k == 1 {
            panic(root.Val)
        }
        k--
        inOrder(root.Left)
    }
    inOrder(root)
    return res
}

结果返回的值是0,那么原因必然是返回值没有接收到res的值,这是因为defer在匿名返回值和命名返回值函数中的表现是不同的
在Golang中,一个有defer语句的匿名返回值函数执行顺序是:
1. 先return将res赋值给一个透明的返回值
2. 然后按后进先出的顺序执行defer语句
3. 最后返回刚创建的透明返回值,函数退出

了解了defer的执行顺序,返回0的原因就很清楚了,因为newVal先被赋值为0,然后才执行defer语句改变了res,但是已经对真正的返回值newVal没有任何影响了。想要解决也很简单,为返回值命名(或者用指针),这样在defer中操作的就是真正的返回值了,代码如下:

func kthLargest2(root *TreeNode, k int) (res int) {
    defer func() {
        res = recover().(int)
    }()
    var inOrder func(root *TreeNode)
    inOrder = func(root *TreeNode) {
        if root == nil {
            return
        }
        inOrder(root.Right)
        if k == 1 {
            panic(root.Val)
        }
        k--
        inOrder(root.Left)
    }
    inOrder(root)
    return
}

需要注意的是,这里并没有对真正可能出现的panic情况做处理。

panic逆后续遍历

最后再看一下另外一道题

输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

func isBalanced(root *TreeNode) (balance bool) {
    balance = true
    defer func() {
        if p := recover(); p != nil {
            balance = p.(bool)
        }
    }()
    var depth func(root *TreeNode) int
    depth = func(root *TreeNode) int {
        if root == nil {
            return 0
        }
        left := depth(root.Left)
        right := depth(root.Right)
        if left-right > 1 || right-left > 1 {
            panic(false)
        }
        if left > right {
            return left + 1
        }
        return right + 1
    }
    depth(root)
    return
}

结语

虽然在OJ中AC是足够了,但这并不是打开panic的正确方式,不应该将正确的答案交给panic来处理,更应该从中学到的是如何正确使用defer。

剑指Offer43题 | 1~n整数中1出现的次数

上一篇

基于Trie(前缀树)实现子网合并

下一篇
评论
头像 发表评论 说点什么
还没有评论