题目描述:从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。

Solutions

  采用广度优先遍历的方式写了如下的代码:

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if pRoot is None:
            return []
        queue = [pRoot]
        res = []
        while queue:
            level = []
            size = len(queue)
            for i in range(size):
                node = queue.pop(0)
                level.append(node.val)
                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)
            res.append(level)
        return res
# 运行时间:28ms
# 占用内存:5792k

  还有另一种类似的解决办法:

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        res=[]
        arr=[]
        arr.append(pRoot)
        cur=0
        #last=1
        while cur<len(arr):
            last=len(arr)
            temp=[]
            while (cur<last):
                temp.append(arr[cur].val)
                if arr[cur].left:
                    arr.append(arr[cur].left)
                if arr[cur].right:
                    arr.append(arr[cur].right)
                cur+=1
            res.append(temp)
        return res
# 运行时间:25ms
# 占用内存:5732k

  剑指 offer 上的解法稍显复杂:

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if not pRoot:
            return []
        res=[]
        res_val=[]
        res.append(pRoot)
        
        nextLevel=0 #表示下一层节点的数目
        toBePrinted=1 #表示当前层还没有打印的节点数
        temp=[]
        while len(res)>0:
            node=res[0]
            temp.append(node.val)
            if node.left:
                res.append(node.left)
                nextLevel+=1
                
            if node.right:
                res.append(node.right)
                nextLevel+=1
                
            del res[0]
            toBePrinted-=1
            if toBePrinted==0:
                res_val.append(temp)
                toBePrinted=nextLevel
                nextLevel=0
                temp=[]
        return res_val
# 运行时间:42ms
# 占用内存:5736k

References

  1. 060. 把二叉树打印成多行