LeetCode-二叉树的层次遍历

给定一个给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。

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

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果:

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


思路。

复习:

  • 深度优先搜索(DFS)

  采用深度作为优先级,以便从跟开始一直到达某个确定的叶子,然后再返回根到达另一个分支。

  • 宽度优先搜索(BFS)

按照高度顺序一层一层访问整棵树,高层次的节点将会比低层次的节点先访问。

方法1:递归

最简单的解法就是递归,首先确认树非空,然后调用递归函数 Depth(node, level),参数是当前节点和节点的层次。

  • 比较访问节点所在的层次 level 和当前最高层次 len(levels) 的大小,如果前者更大就向 levels 添加一个空列表。
  • 将当前节点插入到对应层的列表 levels[level] 中。
  • 递归非空的孩子节点:Depth(node.left / node.right, level + 1)
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        #创建一个空列表
        levels=[]
        #判断这个树是否为空
        if not root:
            return levels

        #创建递归函数Depth
        def Depth(node,level):
            if len(levels)==level:
                levels.append([])
            levels[level].append(node.val)

            #先遍历左节点
            if node.left:
                Depth(node.left,level+1)
            #在遍历右节点    
            if node.right:
                Depth(node.right,level+1)
        #从根开始        
        Depth(root,0)

        #返回遍历后的列表
        return levels


最后修改:2019 年 08 月 08 日 09 : 52 PM
这不叫给钱,是打赏。

发表评论