二叉树的层次遍历

Leetcode Link: 102. 二叉树的层序遍历 - 力扣（LeetCode） (leetcode-cn.com)

题目

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

Attention

此题返回的列表的每个元素，表示每层的节点，也是一个列表，

解法一

思路： 由于该题的输出将每一层的节点都组成了一个子列表，那么该题就需要两个队列，一个表示当前层，一个表示下一层。

题解：

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if root == None:
            return []
        # q1 当前队列，q2下一层队列
        q1 = collections.deque()
        q2 = collections.deque()
        q1.append(root)
        res = []
        while(1):
            # 根据结果，每层节点的值需要组成一个列表
            thisLevel = []
            while(q1):
                curNode = q1.popleft()
                thisLevel.append(curNode.val)
                if curNode.left: q2.append(curNode.left)
                if curNode.right: q2.append(curNode.right)
 
            res.append(thisLevel)
			# 下一层队列为空，说明到低了
            if not q2:
                return res
 
            q1, q2 = q2, q1

解法二

思路：只使用一个队列，利用一个变量来标记当前层和下一层的节点数量。整体的思路和解法一一样。

题解： 下面是我版本

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        
        q = collections.deque()
        q.append(root)
        c1 = 1
        c2 = 0
        res = []
 
        while(1):
            curLevel = []
            while(c1>0):
                c1 -= 1
                cur = q.popleft()
                curLevel.append(cur.val)
                if cur.left:
                    q.append(cur.left)
                    c2 += 1
                if cur.right:
                    q.append(cur.right)
                    c2 += 1
            res.append(curLevel)
            if c2 == 0:
                return res
            c1, c2 = c2, c1

实际上可以对这个版本进一步改进，不需要c1,c2两个变量了，而是通过len(deque)来获取长度，直接用for做

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        
        q = collections.deque()
        q.append(root)
        res = []
        while(q):
            n = len(q) # 当前层节点个数
            curLevel = []
            for _ in range(n):
                cur = q.popleft()
                curLevel.append(cur.val)
                if cur.left: q.append(cur.left)
                if cur.right: q.append(cur.right)
            res.append(curLevel)
        return res

解法三

思路：递归实现，对于层次遍历的递归实现，是需要使用一个指示变量来指示当前的层数，指示变量为几就指示当前的树在第几层，故可以通过下标直接访问res

题解：

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        def recur(cur, indLevel):
            # 递归退出条件
            if cur == None:
                return
            # 判断当前层是不是来过了，没来过要创建*当前层*的节点列表
            if len(res)-1<indLevel: # indLevel是从0开始的
                res.append([])
            
            recur(cur.left, indLevel+1)
            #中序操作，向结果中添加当前节点
            res[indLevel].append(cur.val) 
            recur(cur.right, indLevel+1)
        
        res = []
        recur(root, 0)
        return res

启发和联系

注意与该题的区别从上到下打印二叉树1，它的输出就是个列表，每个元素的也是个列表，所以相对不用这么麻烦。