文章 224
评论 6
浏览 200759
Tree - 107. Binary Tree Level Order Traversal II

Tree - 107. Binary Tree Level Order Traversal II

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

    3
   / \
  9  20
    /  \
   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
}

标题:Tree - 107. Binary Tree Level Order Traversal II
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2019/08/26/1566832536098.html

Nothing just happens, it's all part of a plan.

取消