乐趣区

ARTS-第6周-迭代法后序遍历二叉树-重读-Effective-Go-刷题的拐点

jiezi

ARTS

ARTS 是陈浩（网名左耳朵耗子）在极客时间专栏里发起的一个活动，目的是通过分享的方式来坚持学习。

每人每周写一个 ARTS：Algorithm 是一道算法题，Review 是读一篇英文文章，Technique/Tips 是分享一个小技术，Share 是分享一个观点。

本周内容

本周的 ARTS 你将看到：

  1. 迭代的方式实现二叉树的后序遍历
  2. 重读 Go 官方的 Effective Go
  3. 解算法题能力的第一个拐点

Algorithm

这周的算法题是迭代后序遍历二叉树。

遍历二叉树可能是你能想到的最简单、最基本的算法题之一了，使用递归的方式进行遍历可能不到 10 行代码就能解决。但是，这道题却是 Hard 难度，为什么？

原因很简单，题目中这要附加要求让难度飙升。

Follow up: Recursive solution is trivial, could you do it iteratively?

用迭代的方式来实现后序遍历。其实对于前序和中序遍历来说，迭代的方式并不难实现。只要使用栈的思想，通过迭代维护这个栈就可以模拟递归的节点遍历顺序。即便是暂时想不出来，看一次常规的实现也能轻松理解并记忆，但后序遍历的迭代方式就不那么容易了。后序遍历使用迭代方式不好实现的原因，就是很难在模拟栈的同时保证当前节点在它的左右子节点之后输出。如果不通过一些技巧的话很容易导致代码非常不简洁，要使用多个循环来处理，导致代码可读性很差，也很容易写错。

尝试过各种让人崩溃的迭代后序遍历解法之后，在这里找到了我认为最简单的实现方式，而且前中后序遍历的代码能够保持风格上的一致。下面是我把这个解法翻译成 Golang 的版本。

// 通过迭代模拟递归的先进后出来实现后序遍历
// 前中序遍历来说只需要改变当前节点和其左右子节点的入栈顺序即可
// 非常好的统一了三种遍历
func postorderTraversal(root *TreeNode) []int {var ans []int
    var stack []*TreeNode
    // 先让根节点入栈
    stack = append(stack, root)
    for len(stack) > 0 {top := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if top != nil {
            // 当前节点先入栈，这样出栈时就能保证比子节点后出栈
            // 并且对于已经处理过子节点的节点，会在其再次入栈的时候再压入一个 nil 作为标记
            // 下次遍历到 nil 就直接将 nil 下面的节点出栈
            stack = append(stack, top, nil)
            // 子节点入栈顺序是先右后左，保证出栈先左后右
            if top.Right != nil {stack = append(stack, top.Right)
            }
            if top.Left != nil {stack = append(stack, top.Left)
            }
        } else if len(stack) > 0 {
            // 已处理过子节点的节点直接出栈并加入输出
            top = stack[len(stack)-1]
            ans = append(ans, top.Val)
            stack = stack[:len(stack)-1]
        }
    }
    return ans
}

Review 文章推荐

这周重读了 Go 官方的 Effective Go。这是一本来自官方的 Golang 电子书或者叫长文也可以。文中主要给了解过 Go 基本语法的读者介绍 Go 的一些常见用法或者叫“最佳实践”。因为上一次读的时候因为文章实在太长只是粗略跳读了一遍，这次耐下性子通读还是发现了一些之前没太注意的点。很多地方都或多或少了解一些，但是如果有官方的文章来佐证的话，在开发中再次遇到会更加自信，节省搜索确认的时间从而节约开发时间。

内容方面，这本电子书或者说这篇巨长的文章，个人感觉没有多少地方在谈 effective. 但是很多地方都在谈论 Golang 的习惯用法，即文中所说的 idiom. 这更像是一篇来自官方的 Golang 实践指南。文中对 Golang 几乎每个重要语法都做了深度刚刚好的解释，并给出了非常易于理解的代码示例，而且这些例子都非常好。下面是一些我认为重要的内容。

  • 冒号等号组合的使用注意事项
    https://golang.org/doc/effect…

  • init 函数的建议用法
    https://golang.org/doc/effect…

    Besides initializations that cannot be expressed as declarations, a common use of init functions is to verify or repair correctness of the program state before real execution begins.

  • 方法集 Method Set
    关于 pointer receiver 和 value receiver 以及 pointer method 和 value method

    We pass the address of a ByteSlice because only *ByteSlice satisfies io.Writer. The rule about pointers vs. values for receivers is that value methods can be invoked on pointers and values, but pointer methods can only be invoked on pointers.
    This rule arises because pointer methods can modify the receiver; invoking them on a value would cause the method to receive a copy of the value, so any modifications would be discarded. The language therefore disallows this mistake. There is a handy exception, though. When the value is addressable, the language takes care of the common case of invoking a pointer method on a value by inserting the address operator automatically. In our example, the variable b is addressable, so we can call its Write method with just b.Write. The compiler will rewrite that to (&b).Write for us.

  • 给 http server 注册一个 handler 的流程
    https://golang.org/doc/effect…
  • 下划线占位符的正确用法
    利用下划线占位符的副作用例如需要使用 package 的 init 函数时，可以将 import 的 package 命名为下划线。
  • “组合”Embedding
    一些推荐用法

  • 并发编程
    Channel 的常见用法，其中还对新手常犯的 go func() 闭包使用不当的问题进行了特别说明。同时给出了两种常见的控制并发协程数量的方式。

    the loop variable is reused for each iteration, so the req variable is shared across all goroutines. That’s not what we want. We need to make sure that req is unique for each goroutine.
    一个“无锁”的基于 channel 的 RPC 原型
    基于 channel 的简单漏桶内存池？。
    panic 的习惯用法。

Tip 编程技巧

本周没有编程技巧可讲，大哭……

Share 灵光一闪

最近这段时间一直在坚持每天一道 LeetCode，差不多坚持了一个多月。到目前位置大概刷了 150 多道题，虽然很多题目肯定还是需要看别人的解法才知道怎么做，但刷题的过程已经比刚刚开始的时候轻松很多了。仔细回忆最近刷题的经历，我发现从最初的的甚至 Easy 题都很多做不出来到现在能做出不少 Medium 和很少的 Hard, 这中间经历了一个很明显显的拐点。大概就在差不多刷了 100 题的时候，这个转折点的表现就是对于常规的解题方式比如递归和双指针这种，能够自己写出正确的解法。而且，对于自己想不到解法的题目在看过别人的解法之后能很快理解并且迅速用自己的语言实现。

我把这叫做刷题的“入门”状态。在最开始的痛苦期过去之后，虽然还需要一定的题量提升，但是当初对刷题的恐惧已经几乎消失了。

退出移动版