题目描述

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example: Given binary tree [3,9,20,null,null,15,7],

3 / \ 9 20 / \ 15 7

return its level order traversal as: [ [3], [9,20], [15,7] ]

算法思路

1)加入null标记一层是否结束，使用队列来进行层次遍历 2）第一次加入【root，null】

如果出队列元素不是null，则将出栈元素的左孩子和右孩子加入队列中，重复直到遇到下一个null如果出栈的是null，则说明一层已经完了，需要删除第一个null字符，并新的一层后面加入null

3）如果经过输出之后第一个元素还是null，说明新的一层为空，即所有元素已经输出，结束循环

算法实现

class TreeNode(): def __init__(self,x): self.val=x self.left=None self.right=None class Solution(): def levelOrderTraversal(self,root): res=[] queue=[root,'null'] while queue[0]!='null': temp=[] #如果出队列元素不为null，则将左右孩子入队列，然后继续让队列中元素出来 while queue[0]!='null': node=queue.pop(0) temp.append(node.val) if node.left!=None:queue.append(node.left) if node.right!=None:queue.append(node.right) queue.append('null')#新的一层加入null queue.pop(0)#删除上一层留下来的null if len(temp)!=0: res.append(temp) print(temp) return res #测试 test=Solution() n1=TreeNode(1) n2=TreeNode(2) n3=TreeNode(3) n4=TreeNode(4) n5=TreeNode(5) n6=TreeNode(6) n7=TreeNode(7) n1.left=n2 n1.right=n3 n2.left=n4 n3.left=n5 n3.right=n6 n6.right=n7 """ 1 / \ 2 3 / /\ 4 5 6 \ 7 """ print(test.levelOrderTraversal(n1))

小结

以层为基本单位，层之间的间隔为null，如果这一层没有全部出队列，则需要不断出队列，并把相应孩子节点加入到队列后面。直到遇到null说明这一层已经结束。

要删除上一层留下的null和添加下一层的null，如果新的层为空，说明已经没有元素了，此时可以退出程序，即所有层遍历结束的条件是队列中第一个元素为null。