107. 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]
]

Answer

func levelOrderBottom(root *TreeNode) [][]int {

    if root == nil {
        return [][]int{}
    }

    var result [][]int
    var level []int            //每一层的数值的结果
    stack := []*TreeNode{root} //存储每一层的临时栈

    temp := root     //遍历临时栈时，用的临时变量
    lastMark := root //保存每一层的最后一个节点
    now := root      //下一层的最后一个节点，将来赋值给lastMark标识

    for len(stack) > 0 {

        temp = stack[0]
        level = append(level, temp.Val)
        stack = stack[1:]

        if temp.Left != nil {

            now = temp.Left
            stack = append(stack, temp.Left)
        }

        if temp.Right != nil {
            now = temp.Right
            stack = append(stack, temp.Right)
        }

        if lastMark == temp {
            lastMark = now //把下一行的最后一个赋值给lastMark标识
            result = append(result, level)
            level = []int{}
        }

    }

    for i, j := 0, len(result)-1; i < j; {
        result[i], result[j] = result[j], result[i]
        i++
        j--
    }

    return result

}