(19)Go队列思想实现二叉树的非递归前序和层次遍历

leetcode-144

// 用非递归法实现前序遍历,借用go自带的list实现栈的效果
// go自带的list,推进去的值被包装在element结构里面,element.Value为推进去的值
func preorderTraversal(root *TreeNode) []int {
    if root == nil {
        return nil
    }

    resp := []int{}

    // list底层用双链表实现,对头部尾部的插入取出删除操作时间复杂度都是O(1)
    l := list.New()
    // 从头部插入数据
    l.PushFront(root)

    for l.Len() != 0 {
        // 从头部取出数据,先进后出队列(栈)
        e := l.Front()
        // list底层取出元素后元素不会删除,进行1步删除操作
        l.Remove(e)

        // 断言判定类型
        r, ok := e.Value.(*TreeNode)
        if ok {
            resp = append(resp, r.Val)
        }

        // 先进后出,右先进
        if r.Right != nil {
            l.PushFront(r.Right)
        }
        if r.Left != nil {
            l.PushFront(r.Left)
        }
    }
    return resp
}

提交leetcode，通过

leetcode-102

方法1，借用先进先出队列，再定义多1个结构提element,用layer来存储层数
具体实现如下，速度性能在leetcode上97%，还可以，不过层数有更好的实现方法，看2
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

type element struct {
    layer int //存储层数
    node  *TreeNode
}

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

    e := &element{0, root}
    res := [][]int{}

    l := list.New()
    l.PushFront(e)

    for l.Len() != 0 {
        e := l.Back() //先进先出队列
        l.Remove(e)

        r, ok := e.Value.(*element)
        if ok {
            layer := r.layer
            n := r.node

            if layer < len(res) {
                res[layer] = append(res[layer], n.Val)
            } else {
                res = append(res, []int{n.Val})
            }

            if n.Left != nil {
                l.PushFront(&element{layer + 1, n.Left})
            }
            if n.Right != nil {
                l.PushFront(&element{layer + 1, n.Right})
            }
        }
    }
    return res
}

方法2：leetcode上的最佳解答，作者未知
好好理解，特别是层数的优化方法，不用定义多1个变量layer
func levelOrder2(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }
    res := make([][]int, 0)

    queue := make([]*TreeNode, 0)
    queue = append(queue, root)
    n := len(queue)
    arr := make([]int, 0)

    for len(queue) > 0 {
        node := queue[0]  // 先进先出队列
        queue = queue[1:] 
        arr = append(arr, node.Val)

        n-- // 优化层数的精髓1

        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }

        // 优化层数的精髓2
        if n == 0 {
            res = append(res, arr)
            n = len(queue) // 优化层数的精髓3
            arr = []int{}
        }
    }
    return res
}

leetcode-107

思路：在解决102题目的基础上，对结果进行一次反转即可
func levelOrderBottom(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }

    res := [][]int{}
    arr := []int{}
    l := list.New()
    l.PushFront(root)
    length := l.Len()

    for l.Len() > 0 {
        e := l.Back() // 先进先出队列
        l.Remove(e)
        length--

        r, ok := e.Value.(*TreeNode)
        if ok {
            arr = append(arr, r.Val)

            if r.Left != nil {
                l.PushFront(r.Left)
            }
            if r.Right != nil {
                l.PushFront(r.Right)
            }

            if length == 0 {
                res = append(res, arr)
                arr = []int{}
                length = l.Len()
            }
        }
    }

    // 结果翻转
    i, j := 0, len(res)-1
    for i < j {
        res[i], res[j] = res[j], res[i]
        i++
        j--
    }
    return res
}

提交leetcode，通过