LeetCode 102*. 二叉树的层序遍历(Python)

本文阅读 2 分钟
首页 代码,Java 正文

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

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

    3
   /  <br>   9  20
      /  <br>    15   7

返回其层次遍历结果:

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

 

思路:首先观察返回值格式为一个二维数组,第 i 行表示二叉树的第 i 层,可以使用队列来协助进行层序遍历,队列每一次也传入一个一维数组[ node, level],其中node表示二叉树的节点,level表示该节点所处的层数,每遍历至一个节点就将该节点的左右子节点信息存入队列中去,再从队列中取出一组信息,依次循环。

注意result的行数要随着level的增加而增加,每向下遍历一层,result行数+1

# Definition for a binary tree node.
# class TreeNode:
#     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]]
        """
        import queue

        result = [[]]
        q = queue.Queue()

        if root == None:
            return []
        q.put([root, 0])    # 第一个数据为节点,第二个数据为层数
        while not q.empty():
            temp = q.get()
            node = temp[0]  # 节点
            level = temp[1] # 层数

            if level == len(result):
                result.append([])
            
            result[level].append(node.val)

            if node.left:
                q.put([node.left, level + 1])
            if node.right:
                q.put([node.right, level + 1])
        
        return result

 

本文为互联网自动采集或经作者授权后发布,本文观点不代表立场,若侵权下架请联系我们删帖处理!文章出自:https://wangjiawei.blog.csdn.net/article/details/103508607
-- 展开阅读全文 --
安全面试之XSS(跨站脚本攻击)
« 上一篇 07-24

发表评论

成为第一个评论的人

热门文章

标签TAG

最近回复