把二叉树打印成多行

把二叉树打印成多行_牛客题霸_牛客网

问题简述

给定一个节点数为 n 二叉树，要求从上到下按层打印二叉树的 val 值，同一层结点从左至右输出，每一层输出一行，将输出的结果存放到一个二维数组中返回。

思路1：队列

Python 写法1：一个队列，通过节点数判断层次

class Solution:
    def Print(self , pRoot: TreeNode) -> List[List[int]]:
        if not pRoot: return []
        
        from collections import deque
        
        q = deque()
        q.append(pRoot)
        cnt = 1  # 当前层的节点数
        nxt = 0  # 下一层的节点数
        tmp = []  # 当前层的节点
        ret = []
        
        while q:
            x = q.popleft()
            tmp.append(x.val)
            cnt -= 1
            
            if x.left:
                q.append(x.left)
                nxt += 1
            if x.right:
                q.append(x.right)
                nxt += 1
            
            if not cnt:  # 如果当前层的节点输出完了，打印下一层的节点
                ret.append(tmp[:])
                tmp = []
                cnt = nxt
                nxt = 0
            
        return ret

Python 写法2：两个队列，当前层和下一层

class Solution:
    def Print(self , pRoot: TreeNode) -> List[List[int]]:
        if not pRoot: return []
        
        cur, nxt = [], []
        cur.append(pRoot)
        ret, tmp = [], []
        
        while cur:
            for x in cur:
                tmp.append(x.val)
                if x.left: nxt.append(x.left)
                if x.right: nxt.append(x.right)
            ret.append(tmp[:])
            cur, nxt, tmp = nxt, [], []
            
        return ret

思路2：递归+字典（推荐）

Python

class Solution:
    def Print(self , pRoot: TreeNode) -> List[List[int]]:
        from collections import defaultdict
        
        book = defaultdict(list)
        
        def dfs(x, depth):
            if not x: return
            book[depth].append(x.val)
            dfs(x.left, depth + 1)
            dfs(x.right, depth + 1)
        
        dfs(pRoot, 0)
        # Python 3.6 之后，字典默认是有序的，因此直接打印即可
        return list(book.values())