剑指Offer[32-2]-从上到下打印二叉树

题目

从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。

示例:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果:

[
  [3],
  [9,20],
  [15,7]
]

python代码

class Solution(object):
    def __init__(self):
        self.out_list = []
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        def p(depth,node):
            if node is None:
                return 0
            if len(self.out_list)<depth+1:
                self.out_list.append([])
            self.out_list[depth].append(node.val)
            p(depth+1,node.left)
            p(depth+1,node.right)
        p(0,root)
        return self.out_list

本题的解题思路还是递归的思路(本质就是二叉树的层序遍历)。

  • 因为是层序遍历,所以len(out_list)一定为二叉树的深度;
  • 函数p就是递归的主体;
  • depth用来指示当前节点的层数。

发表评论

电子邮件地址不会被公开。