思路
层序遍历我们需要借助队列来辅助,整体思想就是根入队,然后d出入它的左右子树。一个问题是怎么知道每次出多少个队列元素,因为我们在出队的同时也在入队,因此解决这个问题的办法是针对每一层开始时,我们就先计算好它的原始长度。
type MyQueue struct { queue []*TreeNode } func NewQueue() *MyQueue { return &MyQueue{} } // 头出队 func (mq *MyQueue) pop() *TreeNode { if mq.isEmpty() { return nil } resNode := mq.queue[0] mq.queue = mq.queue[1 :] return resNode } // 入队 func (mq *MyQueue) push(node *TreeNode) { mq.queue = append(mq.queue, node) } func (mq *MyQueue) isEmpty() bool { if len(mq.queue) <= 0 { return true } return false } func levelOrder(root *TreeNode) [][]int { res := make([][]int, 0) if root == nil { return res } mq := NewQueue() mq.push(root) for !mq.isEmpty() { curLevel := []int{} curLen := len(mq.queue) for i := 0; i < curLen; i++ { popNode := mq.pop() if popNode == nil { break } curLevel = append(curLevel, popNode.Val) if popNode.Left != nil { mq.push(popNode.Left) } if popNode.Right != nil { mq.push(popNode.Right) } } res = append(res, curLevel) } return res }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)