二叉树层序遍历

107. 二叉树的层序遍历 II

Difficulty: **给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历） 例如： 给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其自底向上的层序遍历为： [ [15,7], [9,20], [3] ] **

给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：
给定二叉树 [3,9,20,null,null,15,7],

1
2
3
4
5

    3
   / \
  9  20
    /  \
   15   7

返回其自底向上的层序遍历为：

1
2
3
4
5

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

Solution

Language: ****

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrderBottom(root *TreeNode) (res [][]int) {
    var q = list.New()
    if root == nil {
        return res
    }
    q.PushBack(root)
    for q.Len() > 0 {
        size := q.Len()
        temp := make([]int,size)
        var i = 0
        for size > 0 {
            size --
            var front = q.Front() 
            q.Remove(front)
            node := front.Value.(*TreeNode)
            if node.Left!=nil {
                q.PushBack(node.Left)
            }
            if node.Right !=nil {
                q.PushBack(node.Right)
            }
            temp[i] = node.Val
            i++
        
        }
        res = append(res,temp)
    }
    
   
    for i,cnt := 0, len(res) -1;i<cnt ;i,cnt=i+1,cnt-1 {
        res[i],res[cnt] = res[cnt],res[i]
    }

    return res 
}