首页 » Python » 【Leetcode】【python】Binary Tree Level Order Traversal

【Leetcode】【python】Binary Tree Level Order Traversal

原文 http://blog.csdn.net/qqxx6661/article/details/75453452

2017-07-20 06:20:04阅读(189)

题目大意

实现树的广度优先遍历,每一层上的数据按照从左到右的顺序排列。

解题思路

参考:Leetcode-python/102%20Binary%20Tree%20Level%20Order%20Traversal.html" target="_blank">链接
将树每一层的节点存在一个列表中,遍历列表中的元素,如果该节点有左右节点的话,就把它们加入一个临时列表,这样当遍历结束时,下一层的节点也按照顺序存储好了,不断循环直到下一层的列表为空。

代码

BFS

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        tree = []
        if not root:
            return tree
        curr_level = [root]
        # print(type(root), type(curr_level))  # (<class 'precompiled.treenode.TreeNode'>, <type 'list'>)
        # print(curr_level)  # 作为list,却并不能遍历整个树
        while curr_level:
            level_list = []
            next_level = []
            for temp in curr_level:
                level_list.append(temp.val)
                if temp.left:
                    next_level.append(temp.left)
                if temp.right:
                    next_level.append(temp.right)
            tree.append(level_list)
            curr_level = next_level
        return tree

补充:
深度优先DFS

class Solution(object):
    def preorder(self, root, level, res):
        if root:
            if len(res) < level+1: res.append([])
            res[level].append(root.val)
            self.preorder(root.left, level+1, res)
            self.preorder(root.right, level+1, res)
    def levelOrder(self, root):
        res=[]
        self.preorder(root, 0, res)
        return res
总结 正如代码注释,将root外面加括号使得其变为了list。但在下面的for循环中,依然其是作为一个树结构存储的,是否可以理解为这里的括号仅仅是将他变得可被遍历。
之后我print(temp)得到了:
<precompiled.treenode.TreeNode object at 0x7fbb9a294b50>
<precompiled.treenode.TreeNode object at 0x7fbb9a294d50>
<precompiled.treenode.TreeNode object at 0x7fbb9a294d90>
<precompiled.treenode.TreeNode object at 0x7fbb9a294dd0>
<precompiled.treenode.TreeNode object at 0x7fbb9a294e10>

说明确实里面还是树结构。
应该用这个解释来理解,廖雪峰-迭代,可以再看一遍。

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹