Preface

这个世界上优雅的东西很少，递归至少算一个。tree 和 single list 的数据结构，是非常适合使用递归来操作的。下面我们使用 Go 来做几道题，感受一下递归的魅力。

常见问题

1> 反转单链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func reverseList(head *ListNode) *ListNode {
    // 边界情况
    if head == nil || head.Next == nil {
        return head
    }
    var rear = reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return rear // became new head
}

2> 层次遍历二叉树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// LevelTravel 层次遍历实现
func LevelTravel(root *TreeNode) [][]int {
    var s = &solution{}
    s.travel(root, 0)
    return s.result
}

type solution struct {
     result [][]int
}

func (s *solution) travel(r *TreeNode, level int) {
    if r == nil {
        return
    }
    // 扩容
    if len(s.result) <= level {
       s.result = append(s.result, []int{})
    }
    // 将节点值追加到当前层
    s.result[level] = append(s.result[level], r.Val)
    s.travel(r.Left, level+1)
    s.travel(r.Right, level+1)
}