Tree - 107. Binary Tree Level Order Traversal II

ppx

2019-08-26

leetcode

107. Binary Tree Level Order Traversal II

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],

return its bottom-up level order traversal as:

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

思路：

层序遍历二叉树，倒序输出，很简单的实现题，使用slice当做队列就可以。

代码：

go：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrderBottom(root *TreeNode) [][]int {
    var res, out [][]int
    if root == nil {return out}
    
    var curQ = []*TreeNode{root}
    var nextQ []*TreeNode
    var level []int
    
    for len(curQ) != 0 {
        for len(curQ) != 0 {
            cur := curQ[0]
            curQ = curQ[1:]
            level = append(level, cur.Val)
            if cur.Left != nil {
                nextQ = append(nextQ, cur.Left)
            }        
            if cur.Right != nil {
                nextQ = append(nextQ, cur.Right)
            }
        }
        curQ = nextQ
        nextQ = nil
        out = append(out, level)
        level = nil
    }
    
    for i := len(out) -1; i >= 0; i-- {
        res = append(res, out[i])
    }
    return res
}