102. Binary Tree Level Order Traversal

按层次遍历二叉树

思路：类似队列的处理方式，对每一层的放到一个列表里，遍历时将子节点放到新的列表里，然后开始下一层的处理

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        # 6 star
        if not root:
            return []
        rs = []
        queue = [root]
        while queue:
            current_level = queue
            queue = []
            rs.append([i.val for i in current_level])
            for node in current_level:
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return rs

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 6 star, queue存放当前层级的节点，nextLevel存放下一层级的节点，遍历queue,将其中的每个节点的左右节点放入nextLevel, 然后让
// queue=nextLevel, 开始遍历下一层的节点
func levelOrder(root *TreeNode) [][]int {
	if root == nil {return [][]int{}}
	var ret [][]int
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		temp := []int{}

		nextLevel := []*TreeNode{}
		for _, node := range queue {
			temp = append(temp, node.Val)
			if node.Left != nil {nextLevel = append(nextLevel, node.Left)}
			if node.Right != nil {nextLevel = append(nextLevel, node.Right)}


		}
		ret = append(ret, temp)
		queue = nextLevel
	}
	return ret

}