Algorithm

Binary Tree Level Order Traversal II

description

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example: Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

thought

使用bfs算法，每次递归的时候level+1, 这样相同层的节点就可以加到一起。golang这里有个小trick, 每次要判断下level是不是大于或等于len(result), 如果是就要添加一个新的数组。最后再将结果反转一下就是从底层到顶层的顺序。

solution

  1. 递归版本

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

    func levelOrderBottom(root *TreeNode) [][]int {
    var result [][]int
    var traverse func(head *TreeNode, level int)

    traverse = func(head *TreeNode, level int) {
        if head == nil {
            return
        }

        if level >= len(result) {
            result = append(result, []int{})
        }
        result[level] = append(result[level], head.Val)

        traverse(head.Left, level+1)
        traverse(head.Right, level+1)
    }
    traverse(root, 0)

    //reverse  result
    for left, right := 0, len(result)-1; left < right; left, right = left+1, right-1 {
        result[left], result[right] = result[right], result[left]
    }
    return result
}

  2. 使用queue实现非递归版本

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

    func levelOrderBottom(root *TreeNode) [][]int {
    if root == nil{
        return nil
    }

    var result [][]int
    queue := []*TreeNode{root}
    for len(queue) != 0{
        var tmp []int
        for _, v := range queue{
            tmp = append(tmp, v.Val)
            if v.Left != nil{
                queue = append(queue, v.Left)
            }

            if v.Right != nil{
                queue = append(queue, v.Right)
            }
        }
        result = append(result, tmp)
        queue = queue[len(tmp):]
    }

    for left, right := 0, len(result)-1; left < right; left, right = left+1, right-1{
        result[left], result[right] = result[right], result[left]
    }
    return result
}

result

  1. result1

    result1

  2. result2

    result2

Review

The junior developer’s guide to writing super clean and readable code

clean code要像文章一样, 结构清晰，有标题，小标题，章节，这样就能很快的看清楚整个架构。文章整个都是代码类比文章，写代码就像写文章一样，要有明确的标题，章节，格式统一。

怎么做

  1. 格式统一
  2. 使用清晰的变量和方法名
  3. 在必要的时候使用注释
  4. 记住DRY原则(Don’t Repeat Yourself)
  5. 不要过度，提前clean代码

Tip

golang tips

  1. `raw-string`, 多行时可以直接使用，相当于python里面的"""

markdown

  1. backticks输出backticks

    `` `test` ``

Share

使用nginx和uwsgi部署flask应用

参考

  1. Binary Tree Level Order Traversal II
  2. How do I escape a backtick